提出新算法解决动态有向网络下的分布式在线优化问题
A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks
- 融合随机梯度跟踪与方差缩减机制，无需估计度信息
- 理论证明动态遗憾更优，且不依赖梯度有界假设
- 适合资源受限的实时系统，如物联网和边缘计算
随着数据规模与动态性的增加，分布式在线优化在实时决策中变得至关重要。然而，现有算法通常依赖梯度有界假设，并忽视了随机梯度的影响，尤其在时变有向网络中。本文提出一种新型时间变混合随机梯度跟踪算法（TV-HSGT），结合行随机与列随机通信机制，在时变有向图上运行，无需佩龙向量估计或出度信息。通过融合当前与递归随机梯度，有效降低梯度方差，准确追踪全局下降方向。理论分析表明，TV-HSGT可在无梯度有界假设下实现更优的动态遗憾边界。在逻辑回归任务上的实验结果验证了其在动态和资源受限环境中的有效性。
原文摘要 · Abstract (English)
With the increasing scale and dynamics of data, distributed online optimization has become essential for real-time decision-making in various applications. However, existing algorithms often rely on bounded gradient assumptions and overlook the impact of stochastic gradients, especially in time-varying directed networks. This study proposes a novel Time-Varying Hybrid Stochastic Gradient Tracking algorithm named TV-HSGT, based on hybrid stochastic gradient tracking and variance reduction mechanisms. Specifically, TV-HSGT integrates row-stochastic and column-stochastic communication schemes over time-varying digraphs, eliminating the need for Perron vector estimation or out-degree information. By combining current and recursive stochastic gradients, it effectively reduces gradient variance while accurately tracking global descent directions. Theoretical analysis demonstrates that TV-HSGT can achieve improved bounds on dynamic regret without assuming gradient boundedness. Experimental results on logistic regression tasks confirm the effectiveness of TV-HSGT in dynamic and resource-constrained environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。