A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks
This work addresses the problem of real-time decision-making in dynamic, large-scale applications like distributed systems, but it is incremental as it builds on existing gradient tracking methods with specific network adaptations.
The paper tackles distributed online optimization in time-varying directed networks by proposing TV-HSGT, a hybrid stochastic gradient tracking algorithm that eliminates the need for Perron vector estimation and achieves improved dynamic regret bounds without assuming gradient boundedness, with experimental validation on logistic regression tasks.
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.