分布式系统实时追踪动态数据最优解,通过加权策略提升适应性。
Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting
- 用时间加权构建动态目标函数,显式建模流式数据特性。
- 均匀加权下误差衰减为1/t,指数折扣加权存在由衰减因子决定的误差下界。
- 揭示去中心化导致的非零偏差,适合研究分布式在线学习的读者。
传统优化理论多关注固定目标函数,而现代学习系统常在动态环境中运行,数据持续流入,需不断更新决策。本文研究分布式网络中基于流数据的时变优化问题。每个时间步,各代理接收新样本,网络目标是追踪所有历史样本构成的时序加权目标函数的最小值点。考虑通信与计算预算有限的去中心化梯度下降(DGD),每步仅能执行有限次迭代即目标变化。针对强凸平滑损失,通过不动点理论分析追踪误差,发现其由不动点追踪项和由代理间数据异质性引起的偏置项组成。分析了两种自然加权策略:均匀加权(等权重)和指数衰减加权(旧数据影响几何衰减)。均匀加权下,追踪误差收敛速度为 𝒪(1/t);指数加权下,存在由衰减因子控制的非零追踪误差下界。在恒定步长下,去中心化结构引入额外的非零偏置下界。数值实验验证了理论结果。
原文摘要 · Abstract (English)
Classical optimization theory largely focuses on fixed objective functions, whereas many modern learning systems operate in dynamic environments where data arrive sequentially and decisions must be updated continuously. In this work, we study optimization with streaming data over a distributed network of agents. We adopt a structured, weight-based formulation that explicitly captures the streaming-data origin of the time-varying objective: at each time step, every agent receives a new sample, and the network seeks to track the minimizer of a temporally weighted objective formed from all samples observed across the network so far. We focus on decentralized gradient descent (DGD) with a limited communication/computation budget, where at each time step, only a limited number of DGD iterations can be performed before the objective changes again. For strongly convex and smooth losses, we analyze the tracking error with respect to the time-varying minimizer through a fixed-point theory lens. Our analysis reveals that the tracking error decomposes into a fixed-point tracking term and a bias term induced by data heterogeneity across agents. We specialize the analysis to two natural weighting strategies: uniform weights, which treat all samples equally, and exponentially discounted weights, which geometrically decay the influence of older data. Under uniform weighting, DGD tracks the fixed-point at a rate $\mathcal{O}(1/t)$, whereas discounted weighting yields a non-vanishing fixed-point tracking floor controlled by the discount factor. In both cases, decentralization induces an additional non-zero bias floor under a constant step size. We validate our theoretical findings through numerical simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。