具有隐私保护的无投影分布式在线学习算法

陈凯丽 李苏木

摘 要：本文研究了一个具有差分隐私性的无投影分布式在线条件梯度优化问题。针对这一问题，提出了一种分布式在线条件梯度（D-OCG）算法作为期望的变体，该方法通过使用线性最小化步骤来避免投影操作。此问题的网络模型是一个五个节点的平衡无向图。我们在理论证明中知道，该算法对于一般凸局部代价函数的期望遗憾界是O（），其中T是时间范围。我们的结果与最后的理论遗憾，可以实现最先进的算法。最后，通过仿真验证了算法的有效性。

关键词：分布式在线优化;差分隐私;在线梯度;期望遗憾

中图分类号：TP301.6  文献标识码：A  文章编号：1673-260X（2021）01-0004-05

1 引言

近年来，人们对多智能体网络上的凸优化算法越来越感兴趣，由于其在信息控制[1]、机器学习[2]、智能电网[3]等方面的应用。这些应用需要设计分布式优化算法，其中所有节点与它们的即时邻居交换信息，共同达成一个最佳解决方案的共识，该方案将目标函数最小化为局部目标函数的总和[4-8]。

与目标函数随时间变化的经典分布式优化算法相比，分布式在线优化可适用于局部代价函数序列可能以不确定甚至敌对的方式变化的情况。此外，与集中式机器学习算法相比，分布式特性能够完美地将一个大规模问题分解为一系列较小的问题，因此对通信故障和环境的不确定性具有固定的鲁棒性，这使得分布式在线优化算法特别适用于大规模网络。多年来，人们提出了各种分布式在线优化算法。例如，Akbari M，Gharesifard B及Linder L扩展了乘法器的交替方向法（ADMM）[9]，H. F. Xu，Q. Ling及A. Ribeiro提出了无向静态网络的分布式在线优化算法[10]。然而，基于ADMM的算法需要在每次迭代时求解非线性次优问题，这带来了极高的计算量。因此，引入了用于分布式在线优化问题的原对偶算法及其改进方法[11，12]。沿着这样的思路，A. Koppel，S. Paternain和H. Pradhan，A. S. Bedi等人进一步开发了用于求解核希尔伯特空间的随机优化问题的分散在线算法[13，14]。最近，X. Yi，X. Li，L. Xie和K. H. Johansson将在线镜像下降法[16]推广到一个更具有挑战性的案例中[15]，其中，针对时变耦合不等式约束网络的分布式在线优化问题，提出了一种原对偶动态镜像下降算法。Xiong Y，Xu J和You K等人进一步探索一种对实际应用具有较强适应性的算法。利用拉普拉斯机制和重调次梯度技术，提出了一种在线算法，该算法既能解决带行随机矩阵有向图上的分布式约束在线优化问题，又能同时保持一定的差分私密性[17]。尽管这些算法取得了成功，但它们所要求的投影运算仍然限制了它们在许多实际利益的环境中的进一步适用性。为了避免这种代价高昂的操作，Wenpeng Zhang，Peilin Zhao，Wenwu Zhu，Steven C. H. Hoi和Tong Zhang提出了条件梯度的分布式在线变量[18]，并期望它能够通过使用线性最小化步骤来避免投影操作。矩阵学习[19]，多类分类[20]和许多其他相关问题，其中凸域是所有具有有界核范数的矩阵的集合，投影运算相当于计算矩阵的全部的奇异值分解，过于复杂的操作，不能满足分布式在线学习中局部计算的需要。在上述情况下，线性步骤相当于找到一个矩阵的最高奇异向量，这至少简单了一个数量级。然而，如何设计和分析这种变体仍然是一个开放的问题。

为了填补这一空白，我们提出了分布式在线条件梯度（D-OCG）算法作为期望的变体。该算法是对以前的在线变体[21]的一种新的扩展，即每个本地节点将自己的对偶变量与邻居进行交流，以实现相互协作。我们针对一个多类分类任务，评估D-OCG算法在真实数据集上的性能。实验结果表明，D-OCG的运行速度明显快于D-OGD和D-ODA。其每次迭代较低的计算成本及更少的迭代次数，使其成为一个更快的算法。對遗憾界算法的理论结果也得到了很好的验证。

设计在平衡有向图上的隐私保护算法，使所有节点以在线分布的方式，随着时间的推移，令其遗憾度渐近为零。提出了分布式在线条件梯度（D-OCG）算法作为期望的变体，能够通过使用线性最小化步骤来避免投影操作。

2 预备知识及问题描述

在本节中，简要介绍代数图论、隐私分布式在线条件梯度的一些初步内容，并且对具有隐私保护的无投影分布在线算法进行阐述。

2.1 图论

考虑一个由n个节点组成的网络。节点之间的信息共享由有向图G（V，E）来建模，其中V={1，…，n}表示节点的合集，E？哿V×V表示边的合集，A=[aij]n×n ∈Rn×n为其对应的邻接矩阵，所以当（j，i）∈E时，有aij=1，否则aij=0。边（j，i）∈E表示节点i可以从节点j获取信息，设Ni为具有路径传入到节点i的边的邻居的集合，Ni={j：（j，i）∈E}。对于无向图，如果（j，i）∈E，则有aij=aji。

2.2 问题描述

现在，我们制定了差分隐私分布式在线优化问题。在每个迭代t∈[T]，每个节点i∈V在约束集？奂Rm上做出一个决定xi，t，则局部代价函数fi，t：Rm→R关于节点i产生了一个成本函数fi，t（xi，t）。在这种情况下，在每个t时刻，网络的目标是最小化以下代价函数：

fi（x）=fi，t（x），x∈ （1）

这里需要强调的是，每个节点只能访问自己的局部代价函数，而全局函数ft不能被任何单个节点访问。因此，每个节点都需要与其相邻节点进行通信，协同解决优化问题。此外，随着时间的推移，本地成本函数逐渐显现，每个节点i在做出决策前都无法访问fi，t的信息。由于成本函数是时变的，我们需要设计一个算法，在有限的时间范围T>0内，使算法产生的总代价与最优固定决策的代价之差最小。也就是说，如果在提前知道{fi，t}Ti=1所有函数的情况下，累积收益应该尽可能接近最佳固定决策。考虑到隐私问题，网络中的节点通过随机化机制只与相邻节点共享自己的噪声状态，以保护自己的隐私信息。

3 具有隐私保护的无投影分布在线学习算法

在我们的算法中，每个节点i维护两个变量xi，t ∈Rm和zi，t∈Rn，i其初始化分别为xi，0∈和zi，0=ei∈Rn。这里，ei是一个分量等于零的标准向量，除了它的第i个元素等于1。时间t∈[T]，每个节点i生成一个随机噪声向量？浊i，t，这个随机噪声向量？浊i，t来自由高斯分布N（？滓t），参数为？滓t。然后变量xi，t被？浊i，t扰动。具体来说，我们设

yi，t=xi，t+？浊i，t   （2）

之后，每个节点i与它的邻居共享其噪声状态，然后将其状态更新如下：

xi，t+1=bi，t-t  （3）

其中bi，t=∑aijyi，t，gi，t是fi，t在（xi，t）处的次梯度，gi，t=？塄fi，t（bi，t，？浊i，t），t为要设计的步长。zii，t是zi，t的第i个分量，用来平衡次梯度gi，t的辅助变量，辅助变量zi，t更新如下：

zi，t+1=aij（zj，t+？浊i，t）  （4）

我们在算法1中总结了以上内容。

—————————————————————

算法1 隐私分布式在线条件梯度

—————————————————————

1：Input：设置约束;i∈V，随机初始化xi，0∈并设置zi，0=ei;步长t，t∈[T]。

2：for t=0，1，2，…，T-1 do

3： for i=1，…，n do

4：  高斯噪声？浊i，t～N（0，j2）

5：  变量xi，t被？浊i，t扰动并通过（2）得到yi，t

6：  传输yi，t和zi，t给邻居j∈Ni，t

7：  通过（3）更新本地决策xi，t

8：  通过（4）更新辅助变量zi，t

9： end for

10：end for

11：Output：{xi，T}ni=1

—————————————————————

作为本节的结尾，我们给出以下引理来揭示A和变量zii，t的一些重要性质。

引理1 对于t≥0时，有：

1）对于i，j∈V，t≥0，存在0<？孜<1，C>0使得[At]ij-≤C？孜t，zii，t-≤C？孜t;

2）对于i∈V，t≥0，存在>0使得-1≤zii，t ≤1。

4 遗憾界分析

在这一节中，我们研究了一般凸目标函数的遗憾界。

为了得到期望的遗憾界，存在一个不可避免的挑战。即隐私与优化存在冲突，节点不倾向于与相邻节点交换准确的信息以保护自己的隐私，而优化要求节点自由地共享自己的信息来获得准确的最优解。因此，我们必须在隐私级别和优化精度之间建立一个平衡。这个特性是我们的算法与现有的分布式优化算法之间最重要的区别，同时也会给我们的性能分析带来一些技术困难。

如果每个局部代价函数fi，t是一般凸函数，i≥V，t∈[T]，然后我们有下面的定理，揭示了E[Rj（T）/FT]，j≥V的上界在一般凸代价函数上拥有和O（）相同的数量级。此外，在步长选择中使用了一种称为加倍技巧方案[22]的边界技术。

定理1[1] 设x*为对在线优化问题的进行计算的最优解，？浊i，t表示来自高斯分布N（0，j2），？滓t=？驻t/的噪声，{xi，t}Tt=1為算法生成的决策序列。假设步长的选择是通过加倍技巧方案，对于q=0，1，2，…，[log2T]，我们设步长为t=，每周期迭代2q次，t=2q，…，2q+1-1。那么，算法1的遗憾会有上界：

E[Rj（T）|FT]≤B  （5）

其中

B=2（+n）||xi，0||+nR+R2

+

+

+（8n+9）G2  （6）

即E[Rj（T）|FT]=O（）。

证明 我们首先考虑在一个固定的已知时间范围内的有固定步长的期望网络遗憾T′，然后利用加倍技巧方案证明了该定理。

根据[1]中的（16），我们设t==，t∈[T′]，结合事实≥1，我们可以得到：

E[fi，t（xj，t）-fi，t（x*）]

≤（2（+n）||xi，0||+nR

+E[||xi，1-x*||2]+H1）  （7）

其中

H1=

+

++（8n+9）G2  （8）

根据加倍技巧方案，在以2q为迭代次数的周期中，t=2q，…，2q+1-1，q=0，1，2，…，[log2T]，即每一周期的初始值是前一周期的最终值。从（6）中很显然可以看出，E[Rj（T′）]的边界形式为E[Rj（T′）]≤Jq，其中Jq取决于对应周期q的初始条件。那么的直径界限为R<∞，那么就可以得出结论，1/n∑E[||xi，t-x*]||2]≤R2，t≥0。从而可以直接消除相邻周期的依赖关系，在没一个周期q中，期望遗憾界为J，

J=（2（+n）||xi，0||+nR+R2+H1  （9）

因此，网络的总期望遗憾数值可以界定为：

E[Rj（T′）|FT]≤J=J

≤J≤J  （10）

将H1代入到J中會得到（5）中所需的边界。

5 仿真

我们考虑一个由五个节点组成的网络，在权值平衡的无向图上共同估计一个随机向量。图G的拓扑如图1所示。

在每个时刻t∈[T]，每个传感器i∈V权衡一个观测向量zi，t∈R，由于观测噪声的存在，具有不确定性和时变特性。假设每个传感器i具有形式为  hi（）=Hi的线性模型，其中Hi∈R表示观测矩阵，hi（）=0当且仅当=0m。我们的目标是找到能使得函数F（）=fi，t（）最小化的的估计值，其中fi，t（）=||zi，t-Hi||，传感器i在t时刻的观测向量zi，t =Hi+i，t，其中i，t为观测噪声，我们将其假设为白噪声。需要注意的是，由于建模错误和环境中的不确定性的存在，每个成本函数会随着时间变化而变化，事后对时间范围T内的的最佳固定估计是这样给出的：

=HTiHiHTizi，t  （11）

我们考虑m=1的情况。假设的实际值为=1，这对每个传感器都不可用。传感器i在t时刻的观测值为zi，t=ki，t+i，t，其中随机变量ki，t和i，t是分别在均匀分布[kmin，kmax]和[min，max]中抽取的。在整个仿真中，我们设置ki，t∈[0，2]，i，t∈[-1，1]，=[-5，5]。在平衡无向图中设置步长为i，t=1/，i∈V，两种情况：=0.05，=0.1。结果如图2所示，这反映了我们的算法可以实现次线性遗憾，常数决定了隐私水平和优化精度之间的权衡。

最后，我们在图3中用=0.1平均超过100次独立试验来显示每个传感器决策变量的轨迹。它可以观察到传感器的估计方法的实际值=1的期望。

6 总结

本文研究了一个具有差分隐私的无投影分布式在线条件梯度优化问题，该问题的网络模型是具有五个节点的平衡无向图。针对此问题，提出了一种差分隐私分布式在线条件梯度优化算法。特别是采用高斯算法机制来保证个人敏感信息的差异性和私密性。此外，我们推导了一般凸局部代价函数的期望遗憾界，证明了我们的算法可以实现次线性遗憾作为最优理论遗憾。最后，我们通过仿真证明了常数确定了隐私级别和优化精度之间的权衡。

——————————

参考文献：

〔1〕张玲玲.离散多智能体系统在独立位移和速度拓扑结构下的一致性研究[D].2015.

〔2〕邵言剑，陶卿，姜纪远，et al.一种求解强凸优化问题的最优随机算法[J].软件学报，2014，25（09）：2160-2171.

〔3〕张茸擎.网络控制系统的时延与调度算法研究[D].上海交通大学，2007.

〔4〕K. You，R. Tempo，and P. Xie，“Distributed algorithms for robust convex optimization via the scenario approach，” IEEE Trans. Autom. Control，vol. 64，no. 3，pp. 880–895，2019.

〔5〕J. Zhang，K. You，and T. Bas， ar，“Distributed discrete-time optimization in multi-agent networks using only sign of relative state，” IEEE Trans. Autom. Control，2018.

〔6〕J. Xu，S. Zhu，Y. C. Soh，and L. Xie，“A Bregman Splitting Scheme for Distributed Optimization Over Networks，” IEEE Trans. Autom. Control，vol. 63，no. 11，pp. 3809–3824， 2018.

〔7〕J. Xu，S. Zhu，Y. C. Soh，and L. Xie，“Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks，” IEEE Trans. Autom. Control，vol. 63，no. 2，pp. 434–448，2018.

〔8〕C. Liu，H. Li，and Y. Shi，“Distributed Subgradient Method for Convex Constrained Optimization： Non-ergodic Conve gence Guarantees，” arXiv preprint arXiv：1809. 06008， 2018.

〔9〕Akbari M，Gharesifard B，Linder L. Individual Regret Bounds for the Distributed Online Alternating Direction Method of Multipliers[J]. IEEE Transactions on Automatic Control，2019，PP（04）：1-1.

〔10〕H. F. Xu，Q. Ling，and A. Ribeiro，“Online learning over a decentralized network through ADMM，” J. Oper. Res. Soc. of China，vol. 3，no. 4，pp. 537–562，2015.

〔11〕D. Yuan，D. W. Ho，and G. P. Jiang，“An adaptive primal-dual subgradient algorithm for online distributed constrained optimization，”IEEE Trans. Cybern.，vol. 99，pp. 1–11， 2017.

〔12〕A. Koppel，F. Y. Jakubiec，and A. Ribeiro，“A saddle point algorithm for networked online convex optimization，” IEEE Trans. Signal Proces.，vol. 63，no. 19，pp. 5149–5164，2015.

〔13〕A. Koppel，S. Paternain，C. Richard，and A. Ribeiro，“Decentralized online learning with kernels，” IEEE Trans. Signal Proces.，vol. 66，no.12，pp. 3240–3255，2018.

〔14〕H. Pradhan，A. S. Bedi，A. Koppel，and K. Rajawat，“Exact Nonparametric Decentralized Online Optimization，” In Proc. IEEE Global Conf. Signal and Inform. Proces. （GlobalSIP），pp. 643–647，2018.

〔15〕X. Yi，X. Li，L. Xie，and K. H. Johansson，“Distributed online convex optimization with time-varying coupled inequality constraints，” arXiv preprint arXiv：1903.04277，2019.

〔16〕S. Shahrampour，and A. Jadbabaie，“Distributed online optimization in dynamic environments using mirror descent，” IEEE Trans. Autom. Control，vol. 63，no. 3，pp. 714–725，2018.

〔17〕Xiong Y，Xu J，You K，et al.” Privacy Preserving Distributed Online Optimization over Unbalanced Digraphs via Subgradient Rescaling”[J]. IEEE Transactions on Control of Network Systems，2020，pp（99）：1-1.

〔18〕Wenpeng Zhang， Peilin Zhao， Wenwu Zhu， Steven C. H. Hoi， Tong Zhang. Projection-free Distributed Online Learning in Networks. Association for Computing Machinery，2017，pp：4054-4062.

〔19〕Dud′lk，Miroslav，Malick，J′er？ome，et al. Lifted coordinate descent for learning with trace-norm regularization. In International Conference on Artificial Intelligence and Statistics，pp. 327–336，2012.

〔20〕Hazan， Elad and Luo， Haipeng. Variance-reduced and projection-free stochastic optimization. In International Conference on Machine Learning， pp. 235–243，2016.

〔21〕Hazan，Elad. Introduction to online convex optimization. Foundations and Trends R in Optimization，2（3-4）：157–325，2016.