提出一种类型化张量语言,统一描述联邦学习的计算结构。
A Typed Tensor Language for Federated Learning
- 区分客户端张量与共享张量,通过追踪记录轴建模数据分布。
- 证明单轮程序可压缩为固定维度共享状态,规模不随客户端数增长。
- 支持可微分编程,实现梯度下降与二阶优化的类型化联邦训练。
联邦学习与分析常被描述为独立协议,但其数学形式相同:客户端本地张量计算、可合并的聚合到共享状态、仅共享的后处理。我们提出一种类型化张量语言,形式化该结构。语言区分联邦张量(记录按轴划分于各客户端)与共享张量(全局可用)。语义通过虚拟全局张量定义,仅作参考。核心结果为共享状态分解理论:单轮程序可因子化为固定维共享状态,其大小与客户端和记录数量无关,由客户端本地张量表达式计算并跨客户端合并。我们还证明逆向可表示性:若编码器与解码器在语言中可表达,则对应因子化可通过类型化单轮程序实现,且该对应关系可扩展至跨轮共享状态的迭代程序。这为语言中可表示的编码-合并-解码计算提供了形式化解释。随后我们构建可微分片段用于学习。若每记录损失及其梯度由客户端本地张量表达,全局梯度由联邦梯度张量在记录轴上的求和表示。由此得出类型化迭代程序,支持服务器端梯度下降与共享线性代数二阶更新。该框架刻画了一类通信经由固定维度共享状态的联邦学习计算。
原文摘要 · Abstract (English)
Federated learning and analytics are often described as collections of separate protocols, even when they share the same mathematical form: client-local tensor computation, mergeable aggregation into shared state, and shared-only post-processing. We introduce a typed tensor language that formalizes this structure. The language distinguishes federated tensors, whose records are partitioned across clients along a tracked record axis, from shared tensors, which are available globally. Its semantics are defined by comparison with a virtual global tensor, used only as a reference object. The main result is a shared-state factorization theory. We show that typed one-round programs factor through fixed-dimensional shared state whose size is independent of the number of clients and records, computed from client-local tensor expressions and merged across clients. We also prove a converse representability result; factorizations whose encoders and decoders are expressible in the language are realized by typed one-round programs, and the correspondence extends to iterative programs whose cross-round state is shared. This gives a formal account of the computations in the language that can be expressed as encode, merge, and decode procedures. We then develop a differentiable fragment for learning. If a per-record loss and its per-record gradient are represented by client-local tensor expressions, the global gradient is represented by record-axis summation of the federated gradient tensor. This yields typed iterative programs for server-side gradient descent and shared-linear-algebra second-order updates. The framework characterizes a broad class of federated learning computations whose communication passes through fixed-dimensional shared state.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。