论文标题
通过随机变化的图表分散的在线正规化学习
Decentralized Online Regularized Learning Over Random Time-Varying Graphs
论文作者
论文摘要
我们研究了随机时间变化的图表，研究了分散的在线正规化线性回归算法。在每个时间步骤中，每个节点都运行一个在线估计算法，该算法由创新项组成，该算法处理其自己的新测量，共识术语以其自身的估计和邻居的加权量和具有添加性和乘法性通信噪声和正则化术语的加权总和，以防止过度拟合。不需要回归矩阵和图形满足特殊的统计假设，例如相互独立性，时空独立性或平稳性。我们开发了估计误差的非负性超智能不平等，并证明所有节点的估计几乎可以肯定地收敛到未知的真实参数矢量，如果算法获得，图形和回归矩阵可以共同满足样品路径路径时空的激发条件的持久性。尤其是，如果图形统一地共同连接并有条件平衡，并且所有节点的回归模型在有条件地有条件时空共同观察到，则该条件可以通过选择适当的算法增益来获得适当的算法增益，并且在均匀的算法中均匀地有条件地共同观察到，在均匀的算法中，均值在均值和均值中汇聚。此外，我们证明了遗憾的上限为$ O（t^{1-τ} \ ln t）$，其中$τ\ in（0.5,1）$是一个恒定的，取决于算法的增长。
We study the decentralized online regularized linear regression algorithm over random time-varying graphs. At each time step, every node runs an online estimation algorithm consisting of an innovation term processing its own new measurement, a consensus term taking a weighted sum of estimations of its own and its neighbors with additive and multiplicative communication noises and a regularization term preventing over-fitting. It is not required that the regression matrices and graphs satisfy special statistical assumptions such as mutual independence, spatio-temporal independence or stationarity. We develop the nonnegative supermartingale inequality of the estimation error, and prove that the estimations of all nodes converge to the unknown true parameter vector almost surely if the algorithm gains, graphs and regression matrices jointly satisfy the sample path spatio-temporal persistence of excitation condition. Especially, this condition holds by choosing appropriate algorithm gains if the graphs are uniformly conditionally jointly connected and conditionally balanced, and the regression models of all nodes are uniformly conditionally spatio-temporally jointly observable, under which the algorithm converges in mean square and almost surely. In addition, we prove that the regret upper bound is $O(T^{1-τ}\ln T)$, where $τ\in (0.5,1)$ is a constant depending on the algorithm gains.
