0 概述

对偶平均(Dual Averaging, DA)^[1]是求解非光滑约束问题的一阶梯度优化方法, 由经典的投影次梯度方法^[2]和镜面下降算法^[3]改进而来。批处理形式的梯度优化方法在迭代过程中通过遍历样本集来计算损失函数的梯度, 无法满足数据规模急剧增长的需求。然而, 由于机器学习通常假定先验样本集均为独立同分布, 使单个样本对应目标函数的梯度就是训练集上目标函数梯度的无偏估计。因此, 随机形式的DA优化方法在迭代过程中仅需获知目标函数梯度的无偏估计即可^[4]。

在实际应用中, 样本独立同分布的条件未知且无法验证, 被认为是广义的梯度有偏估计问题^[5-7]。对于批处理形式的算法, 文献[8]指出, 当批处理方法中存在固定水平的定性误差时, Nesterov加速算法的收敛速率界随着迭代步数的增加会出现累加定性误差的现象, 而非加速算法的收敛速率界为常量。在此基础上, 文献[9]提出随机优化方法。在处理稀疏优化问题时, 使用优化算法的个体解作为最终输出, 个体解比平均形式的解具有更好的稀疏性。然而, 关于个体解的输出研究较多^[10-11], 但对于单纯的凸问题, 目前经典梯度优化算法的最优个体收敛速率仍是机器学习领域研究的重点。文献[12]提出DA优化方法, 在迭代过程中嵌入线性插值操作, 实验结果表明, 该方法在一般凸情形下具有最优的个体收敛速率。

关于个体收敛性的研究较多^[13], 但较少涉及梯度估计有偏情形。本文研究线性插值随机DA优化方法^[12]的个体收敛界是否随迭代累积偏差的问题。对于有偏梯度估计, 文献[12]利用平均输出的方式得到DA优化方法, 该方法的收敛界不产生累积偏差。对于线性插值DA的优化算法, 由于在收敛性分析过程中对偶空间的复杂度要求, 较难结合偏差进行求解, 因此文献[12]给出其个体收敛界不随噪声偏差累积的预测。本文基于COMID的收敛性分析^[14]给出DA收敛性证明, 在梯度估计有偏差的情形下, 得到正则化损失函数问题的线性插值随机DA不产生累积偏差的个体收敛界, 从而保证算法的个体收敛精度。

1 有偏随机优化

本文研究二分类正则化优化问题。根据文献[16], 有偏随机优化问题描述如下:

$ \min F(\mathit{\boldsymbol{w}}) = r(\mathit{\boldsymbol{w}}) + {E_\xi }[f(\mathit{\boldsymbol{w}},\xi )] $

(1)

其中, w∈$\mathbb{R}$ⁿ是优化变量, 即学习问题的权重, r(w)= λ‖w‖₁为正则化项, 其控制优化变量的稀疏程度, f(w, ξ)=$\frac{{1}}{{n}}\sum\limits^n_{i=1}$l(w, ξ_i)为损失项, 控制优化模型的训练精度, λ为正则化项和损失项的折衷参数, 损失项中的n为训练集中的样本数目, ξ_i=(y_i, x_i)代表第i个样本, y_i∈{+1, －1}为样本标签, x_i∈Rⁿ为样本。该优化问题的目标函数可理解为随机样本造成正则化损失的期望, 此时损失项为f(w)=E_ξ[f(w, ξ)]。由于目标函数是期望形式, 无法直接优化, 但一阶方法在优化过程中仅使用目标函数的梯度信息, 只需对损失的梯度进行估计便可优化求解。根据文献[7], 下文描述有偏情形下的随机优化问题。

定义1  假设训练集样本损失的全梯度为▽f(w), 随机抽取的单个样本损失的函数梯度为▽f(w, ξ), E_ξ[▽f(w, ξ)]=▽f(w)+ε, E_ξ[‖▽f(w, ξ)－▽f(w)‖²]≤σ², 其中, ε∈R为使用随机样本ξ进行梯度估计而产生的误差, σ²为相应的方差。如果ε=0, 则单个随机样本损失的函数梯度为全梯度▽f(w)的无偏估计; 如果ε≠0, 则单个随机样本损失的函数梯度为全梯度▽f(w)的有偏估计, 同时称式(1)为有偏随机优化问题。

对于式(1)描述的优化目标, 文献[9]在目标函数光滑情形下给出有偏随机优化的凸函数性质。对于满足(δ, L)型的目标函数f(w)且w, y∈Q, 有:

$ \begin{array}{l} 0 \le f(\mathit{\boldsymbol{y}}) - f(\mathit{\boldsymbol{w}}) - \left\langle {{g_{\delta L}}(\mathit{\boldsymbol{w}}),\mathit{\boldsymbol{y}} - \mathit{\boldsymbol{w}}} \right\rangle \le \\ \;\;\;\;\;\frac{L}{2}{\left\| {\mathit{\boldsymbol{y}} - \mathit{\boldsymbol{w}}} \right\|^2} + \delta \end{array} $

(2)

其中, f(w)为要优化的目标函数, g_δL(w)为(δ, L)型梯度估计, L为光滑系数, δ为偏差。

近年来, 国内外学者研究了非精确求解有偏随机优化的问题。在文献[8]中, 当批处理方法中存在固定的定性误差时, 梯度优化算法收敛速率界为常量, 而加速算法收敛速率的界却会出现随着迭代的增加而累加定性误差的现象。文献[9]将(δ, L)非精确求解应用到随机优化问题, 给出已知随机偏差δ与方差σ²情形下3种近似梯度下降算法的收敛速率, 即随机一般梯度方法(Stochastic Primal Gradient Method, SPGM)、随机对偶梯度方法(Stochastic Dual Gradient Method, SDGM)和随机快速梯度方法(Stochastic Fast Gradient Method, SFGM)的收敛速率分别为O((L/t+σ/$\sqrt {t} $)lgt+δ)、O(L/t+σ/$\sqrt {t} $+δ)和O(L/t²+σ/$\sqrt {t} $+tδ)^[9]。其中, t为迭代步数。对于存在偏差的优化问题, 随机方法和批处理方法一样, 加速插值策略都会导致偏差δ随迭代累加而达不到任意给定的收敛精度。

2 DA收敛速率证明

对于机器学习约束优化问题, 有:

$ \mathop {\min }\limits_{w \in Q} f(\mathit{\boldsymbol{w}}) $

(3)

其中, Q⊆$\mathbb{R}$ⁿ是有界闭凸集, f(w)是凸函数。

文献[9]在投影次梯度方法和镜面下降算法的基础上, 提出DA方法, 其迭代方式为:

$ {\mathit{\boldsymbol{w}}_{t + 1}} = \mathop { \rm argmin }\limits_{w \in Q} \left\{ {\left\langle {\sum\limits_{k = 0}^t {{a_k}} \nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right),\mathit{\boldsymbol{w}}} \right\rangle + {\gamma _t}d(\mathit{\boldsymbol{w}})} \right\} $

(4)

其中, α_t为学习速率, γ_t为步长参数, 其可以使学习速率α_t的选取更加灵活, 能够以多种取值使收敛速率达到最优, d(w)为近邻函数, 满足强凸性质。

$ d\left( \mathit{\boldsymbol{y}} \right) \ge d\left( \mathit{\boldsymbol{w}} \right) + \left\langle {\nabla d\left( \mathit{\boldsymbol{w}} \right),\mathit{\boldsymbol{y}} - \mathit{\boldsymbol{w}}} \right\rangle + \frac{1}{2}{\left\| {\mathit{\boldsymbol{y}} - \mathit{\boldsymbol{w}}} \right\|^2} $

(5)

其中, w∈Q, y∈Q。

引理1  对于d(w)满足强凸性质, w_k由算法本身产生, f(w)为一般凸函数^[17]。对任意w∈Q, 强凸极值为:

$ \begin{array}{l} \left\langle {\sum\limits_{k = 0}^t {{a_k}} \nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right),\mathit{\boldsymbol{w}}} \right\rangle + {\gamma _t}d(\mathit{\boldsymbol{w}}) \ge \left\langle {\sum\limits_{k = 0}^t {{a_k}} \nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right),{\mathit{\boldsymbol{w}}_{t + 1}}} \right\rangle + \\ \;\;\;\;\;\;\;\;{\gamma _t}d\left( {{\mathit{\boldsymbol{w}}_{t + 1}}} \right) + {\gamma _t}/2{\left\| {\mathit{\boldsymbol{w}} - {\mathit{\boldsymbol{w}}_{t + 1}}} \right\|^2} \end{array} $

(6)

引理2  对任意w∈Q, 有:

$ \begin{array}{l} \sum\limits_{k = 0}^N {\left\langle {{a_k}\nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right),{\mathit{\boldsymbol{w}}_k} - {\mathit{\boldsymbol{w}}_{t + 1}}} \right\rangle } - {\gamma _t}d\left( {{\mathit{\boldsymbol{w}}_{t + 1}}} \right) \le - {\gamma _0}d\left( {{\mathit{\boldsymbol{w}}_1}} \right) + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{k = 0}^t {\frac{{a_k^2}}{{2{\gamma _k}}}} {\left\| {\nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right)} \right\|^2} \end{array} $

(7)

定理1  上述引理条件不变, d(w)满足强凸性质, w_k由算法本身产生, f(w)为一般凸函数。对任意w∈Q, 有:

$ \begin{array}{l} \frac{1}{{{A_t}}}\sum\limits_{k = 0}^t {{a_k}} f\left( {{\mathit{\boldsymbol{w}}_k}} \right) - f\left( {{\mathit{\boldsymbol{w}}_*}} \right) \le \frac{1}{{{A_t}}}\left[ {\sum\limits_{k = 1}^t {\frac{{a_k^2}}{{2{\gamma _{k - 1}}}}} {{\left\| {\nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right)} \right\|}^2} + } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {{\gamma _t}d\left( {{\mathit{\boldsymbol{w}}_ * }} \right)} \right] \end{array} $

(8)

与文献[9]方法结论相同, 在选取a_t=1、γ_t=O($\sqrt {t} $)时, 对偶平均优化算法收敛速率能达到最优O(1/$\sqrt {t} $)。其中, w_*为式(1)的最优解。A_t的计算公式为:

$ {A_t} = \sum\limits_{k = 0}^t {{a_k}} $

(9)

文献[9]在原对偶平均方法的迭代中嵌入一步线性插值操作^[12], 对于一般凸的情形同样在选取a_t=1、γ_t=O($\sqrt {t} $)或者a_t=t、γ_t=O(t$\sqrt {t}$)时, 对偶平均优化算法能得到最优的个体收敛速率O(1/$\sqrt {t} $)。迭代步骤为:

$ \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{w}}_t^ + = \arg \min \left\{ {\sum\limits_{k = 0}^t {\left\langle {{a_k}\nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right),\mathit{\boldsymbol{w}}} \right\rangle } + {\gamma _t}d(\mathit{\boldsymbol{w}})} \right\}}\\ {{\mathit{\boldsymbol{w}}_{t + 1}} = \frac{1}{{{A_{t + 1}}}}\left[ {{a_0}{\mathit{\boldsymbol{w}}_0} + \sum\limits_{k = 0}^t {{a_{k + 1}}} \mathit{\boldsymbol{w}}_k^ + } \right]} \end{array}} \right. $

(10)

文献[18]将该插值方法推广到投影次梯度方法, 得到个体输出形式下的最优收敛速率。但将文献[12]直接引入投影次梯度方法^[2], 无法得到个体输出的最优收敛速率, 需要在优化算法中增加一个迭代步并修改步长参数, 该方法得到的结论是对投影次梯度方法直接输出个体解问题的一种延伸和拓展, 其迭代计算公式为:

$ \left\{ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{w}}_t^ + = {P_Q}\left( {\mathit{\boldsymbol{w}}_{t - 1}^ + - {a_t}{\tau _t}\nabla f\left( {{\mathit{\boldsymbol{w}}_t}} \right)} \right)}\\ {{\mathit{\boldsymbol{w}}_{t + 1}} = \frac{{{A_t}}}{{{A_{t + 1}}}}{\mathit{\boldsymbol{w}}_t} + \frac{{{a_{t + 1}}}}{{{A_{t + 1}}}}\mathit{\boldsymbol{w}}_t^ + } \end{array}} \right. $

(11)

其中, t≥1, P_Q是Q上的投影算子, a_t和τ_t为学习速率参数。

3 梯度有偏差对偶平均方法的个体收敛速率

正则化损失函数是机器学习监督学习算法的基本框架, 不同的分类采用不同的损失, 如光滑损失有最小二乘损失和对数损失, 非光滑损失即hinge损失。常用正则化项L1、L2进行正则化, 考虑到个体解的稀疏性, 本文采用L1正则化项。本文基于非光滑稀疏学习问题, 对标准的L1正则化hinge损失进行目标优化。

对于式(1)描述的问题, 有:

$ \min F(\mathit{\boldsymbol{w}}) = r(\mathit{\boldsymbol{w}}) + {E_\xi }[f(\mathit{\boldsymbol{w}},\xi )] $

本文采用线性插值DA^[12]的方法进行迭代。

引理3  设Q为L1正则化hinge损失优化问题的约束域, 则Q=[－1/λ, 1/λⁿ]。

证明  设优化问题的最优解为w^*=$\mathop {\arg \min }\limits_w $F(w)。由于正则化项r(w)= λ‖w‖₁, λ为正则化项与损失函数项的折衷参数。hinge损失项f(w; x, y)=max{0, 1－y〈w, x〉}, w表示数据样本, y为数据对应的样本标签, (x_i, y_i)独立同分布, 因此F(w^*)≤F(0)=1, 即‖w^*‖₁≤1/λ。由于‖w^*‖≤‖w^*‖₁≤1/λ, 因此求解优化问题的优化算法的解序列应满足w_t∈Q=[－1/λ, 1/λ]ⁿ, 即优化问题的约束域为w∈Q=[－1/λ, 1/λ]ⁿ。

由引理3可以看出, 本文研究的L1正则化hinge损失的随机优化问题具有相应的约束域。此时, 令$\max\limits_{ \mathit{\boldsymbol{w}}_a, \mathit{\boldsymbol{w}}_b∈Q}$‖w_a-w_b‖≤d, d∈$\mathbb{R}$⁺, 于是∃δ∈$\mathbb{R}$⁺满足〈ε, w-w_t〉≤εd≤δ。设单个样本损失的函数梯度▽f(w_t, ξ)=g_t, 由E_ξ[▽f(w, ξ)]=▽f(w)+ε可得:

$ f(\mathit{\boldsymbol{w}}) - f\left( {{\mathit{\boldsymbol{w}}_t}} \right) - \left\langle {{\mathit{\boldsymbol{g}}_t},\mathit{\boldsymbol{w}} - {\mathit{\boldsymbol{w}}_t}} \right\rangle \le \frac{1}{2}{\left\| {\mathit{\boldsymbol{w}} - {\mathit{\boldsymbol{w}}_t}} \right\|^2} + \delta $

(12)

其中, 估计误差可以和梯度估计误差ε统一归结为偏差δ。

根据定义1, 对于有偏随机优化形式, 嵌入线性插值的对偶平均方法的个体收敛速率如定理2。

定理2  算法的收敛界分析:

$ \begin{array}{l} E\left[ {f\left( {{\mathit{\boldsymbol{w}}_t}} \right) - f\left( {{\mathit{\boldsymbol{w}}_*}} \right)} \right] \le \frac{1}{{{A_t}}}\left[ {\sum\limits_{k = 1}^t {\frac{{a_k^2}}{{2{\gamma _{k - 1}}}}E\left[ {{{\left\| {\nabla f\left( {{\mathit{\boldsymbol{w}}_k}} \right)} \right\|}^2}} \right] + } } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {{\gamma _t}d\left( {{\mathit{\boldsymbol{w}}_*}} \right)} \right] + \delta \end{array} $

(13)

其中, δ为偏差的固定收敛界。

由引理3和定理2可知, 与文献[9]和文献[15]结论不同, 本文证明了线性插值技巧在梯度估计存在偏差时, 偏差并不会随着迭代步数的增加而累积, 收敛速率最后会收敛于某一固定界。这使得线性插值求解个体收敛速率的方法具有一定的实际意义, 且不会因为现实中样本的分布或噪声与理论不符。

推论1  在选取a_t=1、γ_t=O($ \sqrt {t} $)时, 算法收敛速率能收敛到O(1/$\sqrt {t}$)+δ的固定界, 从而偏差不会累积。

文献[19]对标准正则化投影次梯度算法定义proximal mapping, 将正则化项进行改进, 得到与投影算子相似的proximal mapping, 利用文献[2]方法对其最优收敛速率进行证明, 得到正则化形式一阶梯度经典方法的最优收敛速率, 并将其应用到对偶平均方法, 从而得到正则化对偶平均方法在有偏随机优化情形下的个体收敛速率, 进一步验证本文的结论。

4 实验结果与分析

本节通过人工数据集和Libsvm网站上的真实数据集对线性插值随机DA优化方法进行验证。在人工数据集中, 嵌入线性插值的对偶平均方法在有偏随机优化中, 随机噪声的误差不会随迭代步数增加而无限累积。在真实数据集中, 使用文献[13]和文献[15]算法作为对比, 在5个真实库上验证本文算法的收敛性和稳定性。

本文实验采取随机方法抽取样本, 算法分别取相同的约束参数运行10次, 取10次运行结果的平均值作为输出。

4.1 人工数据集

为验证算法理论分析的正确性, 本文给出人工数据集的描述。参考文献[5]和文献[7]中建立人工数据集的基本方法, 选择解向量w(每一维符合正态分布N(0, 1), 再随机抽取10%分量置0), 训练样本矩阵x∈$\mathbb{R}$^{10 000×10 000}(每个分量也符合正态分布N(0, 1), 再每列随机抽取10%置0)。令样本i的标签y_i=Sgn(x_iw), 当y_i>0时, 置y_i=+1为正样本; 当y_i < 0时, 置y_i=－1为负样本, 测试数据同理。在理论上设定得到的次梯度E_ξ[▽f(w, ξ)]=▽f(w)+ε, 在实验中相应会在次梯度的值上加一个符合正态分布N(θ, 1)的随机噪声ε。

图 1给出嵌入线性插值的对偶平均方法在梯度估计存在不同期望值大小随机噪声的收敛趋势及其不同情形下的收敛界。其中, 坐标采用对数坐标系, 横坐标表示迭代步数, 最大值设为1 000, 纵坐标表示相对目标函数值即当前值与最优值之差, 最优值通过Matlab中的CVX工具箱针对现有模型计算得到, 三角形标注实线RDA_OPJ1、正方形标注实线RDA_OPJ2、光滑实线RDA_OPJ3分别表示梯度估计偏差期望值为10、1和0时, 线性插值对偶平均方法的个体解的收敛趋势, 3条虚线分别表示其对应的bound线。可以看出, 在梯度估计存在随机噪声干扰的人工数据集上, 随着迭代步数不断增加, 该算法加入3种期望值随机噪声的曲线最终都收敛于某一定值, 且低于其收敛界对应的bound线, 不会累积或发散。偏差期望值为1的曲线相比无偏差情形在前期波动较大, 但最终会收敛, 与无偏差相距较小。偏差为10的曲线波动不大, 但由于偏差值的影响相比另外2种收敛速率较慢且精度较低。实验结果验证了本文结论的正确性。

4.2 真实数据集

本节对线性插值对偶平均方法的个体收敛性和实时稳定性进行验证, 使用文献[13]提出的嵌入加速算法步长策略的投影次梯度(PGD_step)方法和文献[15]提出的随机加速(SFGM)方法进行对比, 采用来自台湾大学Libsvm网站的5个真实数据集:a9a, astro, rcv1, covtype, CCAT。表 1给出真实数据集的基本描述。

3种算法的收敛速率对比如图 2所示。其中, 横、纵坐标含义与图 1相同, 迭代最大值设为10 000。基准集目标函数最优值未知, 选取各算法迭代10次平均的最小函数值作为目标函数最优值。

从图 2可以看出, 基于非光滑目标函数的嵌入加速算法步长策略的投影次梯度算法具有更快且精度更高的收敛速率, 稳定性较好。与PGD_step方法和SFGM方法相比, 线性插值对偶平均方法的收敛速率较快, 且收敛精度高, 验证了本文方法的正确性。线性插值对偶平均方法对于少数真实数据集, 如a9a和covtype, 稳定性会出现波动, 这是因为使用个体作为输出。综上, 实验验证了本文方法理论分析的正确性, 且具有实际应用意义^[20]。

5 结束语

本文提出一种梯度有偏随机DA优化方法。基于递归思想对凸条件下对偶平均方法的最优收敛速率进行证明。结合线性插值, 将DA应用于非光滑有偏随机优化方法, 得到收敛于固定值的个体收敛界, 且偏差不会随迭代步数的增加而累积。对非光滑有偏随机优化问题进行验证, 结果表明, 线性插值对偶平均方法的收敛速度较快, 且收敛精度较高。后续考虑将加速算法应用于有偏随机优化问题, 进一步提高个体的收敛速度和精度。