基于因子化梯度跟踪的去中心化低管秩张量估计

《Neurocomputing》：Decentralized low tubal rank tensor estimation via factorized gradient tracking

　　

摘要
本文研究了在分布式环境下具有低管秩结构的张量恢复问题。通过将感兴趣的张量分解为两个张量因子，我们使用因子分解梯度下降来计算共识解，并采用惩罚项来强制张量因子间的平衡性。为了更好地在去中心化网络上整合局部信息，采用了因子分解梯度跟踪来近似全局梯度。尽管由于张量分解导致问题是非凸的，但建立了该方法直至统计误差的局部线性收敛性。进行了数值实验以展示估计性能和收敛行为。

引言
张量，作为高阶数据的自然表示，在机器学习、统计分析以及许多其他领域引起了越来越多的关注。张量产生了大量的多维数据应用，例如图像/视频处理 [1], [2]，电子显微镜成像 [3] 和国际商品贸易流 [4]。这些问题通常涉及低秩张量估计。在本文中，我们考虑了一个去中心化网络上的原型张量估计模型，其中是待估计的张量参数，和分别表示系统中的代理数量和局部样本大小（为了符号简单，我们假设所有代理上的局部样本大小相同）。所考虑的网络由个节点通过条边连接，可以用无向图描述。这里，表示节点集，是边集。
模型可以更紧凑地写为
其中是一个线性映射。更具体地说，是第个代理上使用局部测量张量进行线性映射的结果
我们的目标是根据分布在网络上的数据来估计。
在许多实际应用中，中的参数数量很大。因此，通常使用一些结构假设来降低维度。低秩条件在文献中被广泛探索 [5], [6], [7]。在这项工作中，我们假设具有低管秩，
基于张量 - 张量积（t 积）[1], [8] 概念的管秩的正式定义在第 2 节中回顾。结合模型（2）和假设（3），我们将优化问题表述为
其中和。然而，上述公式化的问题是非凸的且难以求解。为了解决这个问题，一种常见的策略是使用张量核范数 [1], [9], [10], [11]，它是秩函数的凸松弛。然而，相关的极小化问题需要计算 t 积奇异值分解（t-SVD），这很耗时。此外，由于核范数只是秩函数的近似，这种方法往往会产生次优结果。因此，许多工作转向流形和/或非凸优化方法 [2], [4], [12], [13], [14]。
在这项工作中，我们使用因子分解方法，写为
其中，，并且表示在下节中定义的的共轭转置。问题（4）随后可以重写为
其中，我们使用梯度方法更新。这种基于因子分解的方法在矩阵估计中得到了很好的研究 [15] [?]。类似的因子分解策略也被用于张量恢复 [2], [13]。然而，这些工作没有考虑分布式环境下的张量恢复。在这项工作中，我们专注于基于去中心化网络上因子分解梯度下降的分布式张量恢复，并旨在建立其向目标值快速收敛。
本文的主要贡献是首次证明梯度跟踪，这是一种在去中心化优化中成熟的技术，可以有效地适应于解决去中心化低管秩张量估计这一具有挑战性的问题，并带有严格的收敛保证。具体而言，我们做出了以下贡献：
• 对于去中心化张量恢复问题，我们提出了一种基于张量因子分解的计算高效方法。我们将一个大的感兴趣张量分解为两个较小张量因子的 t 积，并使用分布式因子分解梯度下降来解决由此产生的非凸问题。此外，采用梯度跟踪来近似全局梯度。
• 施加惩罚项以鼓励两个张量因子之间的平衡性，旨在减少因子之间的差异并增强收敛性。据我们所知，这种平衡惩罚尚未用于去中心化环境下的 t 积张量因子分解。
• 在收敛性分析中，利用三个误差度量的一步界，包括（i）不同代理之间的共识误差，（ii）平均估计的误差，以及（iii）梯度跟踪误差，我们建立了所提出的算法实现了直至统计误差的局部线性收敛，尽管问题相对于张量因子是非凸的。在非凸张量环境中需要跟踪三个耦合的误差度量，加上由正交模糊性引起的商几何，超出了标准的梯度跟踪分析。
• 进行了一些数值实验来验证我们提出的去中心化张量恢复算法的有效性和收敛性。还研究了各种量对收敛和估计的影响。
1）去中心化优化。去中心化网络是一种特殊的分布式网络拓扑。对于中心化网络，存在一个连接所有其他本地机器的主节点。主节点收集优化所需的变量，然后产生输出。在统计社区中，分而治之方法 [?] [16], [17] 发展良好，其中主节点聚合由本地节点生成的估计。相比之下，去中心化网络去除了主节点，形成了一个点对点系统，其中每台机器只连接到一部分相邻节点 [18]，并且比中心化网络更稳定和高效 [19]。值得注意的是，主机的缺失使得大多数为中心化网络设计的算法无法应用。这促使许多研究人员研究去中心化方案，并提出了各种去中心化算法 [18], [19], [20], [21], [22], [23], [24]。其中，[19] 提出了去中心化交替方向乘子法，已被广泛应用于各种应用 [25], [26]。分布式梯度下降 [23], [24] 及其近端/投影变体 [21], [22] 也很流行。然而，这些方法都没有考虑去中心化环境下的非凸低管秩张量估计问题。
2）低秩张量恢复。虽然低秩张量恢复推广了低秩矩阵恢复的概念 [15] [?]，但它引入了额外的挑战，且张量的秩定义不是唯一的。这些包括 Tucker 分解，CONDECOMP/PARAFAC (CP) 分解 [27]，以及基于 t 积的分解 [8]。对于张量估计，[28] 提出了张量补全的核范数之和，[1] 开发了用于张量鲁棒主成分分析的 t 积张量核范数，这促进了随后在 [5], [9], [10], [29] 中的应用。此外，[11] 开发了张量限制性等距性质，并在此假设下建立了恢复保证。还提出了其他范数来近似秩函数，例如张量 Schatten-p 范数 [30]，加权张量核范数 [31] 以及其他一些 [2], [14]。张量因子分解是一种捕获低秩结构的策略。随着不同的张量分解，它产生了各种方法，包括通过 CP 分解的梯度下降 [32] 和通过 Tucker 分解的黎曼流形优化 [4], [12]。基于 t 积的分解在张量恢复中也受到了大量关注，这避免了矩阵展开，从而更好地保留了结构信息 [7], [13]。然而，这些都没有考虑去中心化环境下的分布式张量恢复。特别地，虽然梯度跟踪已成功应用于各种去中心化共识优化问题 [22], [33], [34]，但其在具有 t 积的非凸张量因子分解中的应用尚未得到探索。类似地，低管秩张量恢复的因子分解梯度下降 [7] 和相关非凸方法 [13] 是专门为所有数据都可在单台机器上获得中心化环境开发的。我们的工作通过考虑这两种范式，梯度跟踪和张量因子分解，来填补这一空白，以解决去中心化低管秩张量估计问题。
本文其余部分组织如下。第 2 节回顾了张量 - 张量积（t 积）的基本概念，第 3 节提出了带有梯度跟踪的低管秩张量恢复的去中心化因子分解梯度下降算法。第 4 节建立了算法的收敛性。第 5 节展示了一些数值实验。第 6 节总结本文并进行一些讨论。
符号。我们将向量表示为粗体小写字母（），矩阵表示为粗体大写字母（），张量表示为粗体欧拉花体字母（）。我们使用和分别表示矩阵的 Frobenius 范数、算子范数和核范数。和的内积定义为，其中是对张量的向量化操作，张量的 Frobenius 范数为。的第个前向片表示为（在本文中所有张量都是三阶的），或表示其第个条目。

章节片段
张量 - 张量积
在本节中，我们回顾张量 - 张量积（t 积）和相关操作的概念。对于张量，设是块循环矩阵化算子，定义为
块向量化算子及其逆算子通过
定义。
定义 1 t 积，[8]
给定任意和，t 积定义为
用表示 DFT（离散傅里叶变换）矩阵，其中和。我们知道，因此。然后，块循环矩阵可以块对角化为
其中由获得。由（6），我们有
定义 2 共轭转置，[1]
对于任意，
分布式低管秩张量估计
回顾优化问题（5），
注意我们总能找到一对满足平衡性的一对解。例如，令是的 t-SVD，那么平衡性对于成立，其中是使得。此外，显然对于任意正交张量，对也满足平衡性，这意味着对不是唯一的。为了鼓励平衡性，受 [15] [?] 启发，我们添加了一个惩罚，导致以下公式
据我们所知，
收敛性分析
在本节中，我们研究所提出的去中心化张量恢复算法的收敛性，为此还需要以下假设。
假设 2 是强凸且平滑的，具有正常数，分别为。即和成立。此外，对于，也是具有参数的平滑的。
备注 1
我们强调假设 2 涉及原始张量参数，而不是因子分解变量。具体而言，它指出目标相对于是 - 强凸和 - 平滑的，
数值研究
在本节中，我们通过进行一些计算实验来研究我们提出的去中心化张量估计（在以下用 DecTE 表示）的数值行为。
结论与讨论
在本文中，我们通过带有梯度跟踪的因子分解梯度下降研究了去中心化低管秩张量恢复问题。尽管由于因子分解问题是非凸的，但我们建立了所提出算法直至统计误差的局部线性收敛性。进行了一系列数值实验来展示算法的收敛行为和估计性能。
有一些有趣的话题有待探索。为了
CRediT 作者贡献声明
Zihao Song：方法论，形式分析，数据管理。Ling Peng：方法论，软件，验证，可视化，写作 - 审阅与编辑。Weihua Zhao：写作 - 初稿，监督，形式分析。Heng Lian：写作 - 审阅与编辑，方法论，形式分析，概念化。
竞争利益声明
作者声明他们没有任何已知的竞争性财务利益或个人关系，这些可能会影响本文中报道的工作。
Zihao Song 是统计学和应用数学领域的研究人员，最近隶属于南通大学。他的研究专注于张量数据分析、低秩张量恢复、鲁棒统计学习和高维推断。他最近的出版物包括关于低管秩张量补全、鲁棒低管秩张量恢复、鲁棒张量回归和半监督高维推断的工作。
Zihao Song|Ling Peng|Weihua Zhao|Heng Lian
南通大学数学与统计学院，中国南通