Comparing Decentralized Gradient Descent Approaches and Guarantees
Comparing Decentralized Gradient Descent Approaches and Guarantees
复制标题
DOI：
10.1109/icassp49357.2023.10096994
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Shana Moothedath;Namrata Vaswani
中科院分区：
文献类型：
--
作者：
Shana Moothedath;Namrata Vaswani
这项工作研究了我们最近开发的分散算法，分散交替投影梯度下降算法，称为Dec-AltProjGDmin，用于解决以下低秩（LR）矩阵恢复问题：从独立列线性投影（LR列压缩感知）恢复LR矩阵。在最近的工作中，我们在简单的假设下提出了Dec-AltProjGDmin的建设性收敛保证。所谓“构造性的”，我们的意思是提供了实现任何误差水平ε的收敛时间下限。然而，我们的保证是针对等邻居共识算法（在每次迭代中，每个节点计算其所有邻居的数据的平均值），而大多数现有的结果并不假设使用特定的共识算法，而是根据权重矩阵特征值进行状态保证。为了与这些结果进行比较，我们首先将我们的结果修改为这种形式。我们的第二个也是主要贡献是将我们的新结果与分散GD文献中现有的最佳结果进行了理论和实验比较，该文献还提供了足够大的ε值的收敛时间界。现有的保证是针对不同的问题设定，并在与我们不同的假设下成立，因此比较并不十分明确。然而，我们也不知道在任何其他设置中用于分散式LR矩阵恢复的任何其他可证明正确的算法。
This work studies our recently developed decentralized algorithm, decentralized alternating projected gradient descent algorithm, called Dec-AltProjGDmin, for solving the following low-rank (LR) matrix recovery problem: recover an LR matrix from independent column-wise linear projections (LR column-wise Compressive Sensing). In recent work, we presented constructive convergence guarantees for Dec-AltProjGDmin under simple assumptions. By "constructive", we mean that the convergence time lower bound is provided for achieving any error level ε. However, our guarantee was stated for the equal neighbor consensus algorithm (at each iteration, each node computes the average of the data of all its neighbors) while most existing results do not assume the use of a specific consensus algorithm, but instead state guarantees in terms of the weights matrix eigenvalues. In order to compare with these results, we first modify our result to be in this form. Our second and main contribution is a theoretical and experimental comparison of our new result with the best existing one from the decentralized GD literature that also provides a convergence time bound for values of ε that are large enough. The existing guarantee is for a different problem setting and holds under different assumptions than ours and hence the comparison is not very clear cut. However, we are not aware of any other provably correct algorithms for decentralized LR matrix recovery in any other settings either.