A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks

Xinli Shi, Xingxing Yuan, Longkang Zhu, Guanghui WenarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces TV-HSGT, a novel algorithm for distributed online optimization in dynamic, directed networks. It tackles the challenge of noisy, time-varying data by combining a hybrid variance reduction technique with a gradient tracking mechanism, achieving improved dynamic regret bounds without requiring bounded gradients.

What Problem Does This Paper Address?

In today's data-rich world, many applications require real-time decision-making based on continuously changing information. This is known as online optimization. When these decisions are made by multiple agents communicating over a network, it becomes distributed online optimization. Existing methods often struggle with:

  • Time-varying data: The optimal solution can change over time, making it hard for algorithms to keep up.
  • Stochastic gradients: Real-world data is often noisy, leading to inaccurate gradient estimates.
  • Directed networks: Communication links might not be bidirectional, and the network structure can change over time.
  • Bounded gradient assumptions: Many algorithms assume gradients don't change too drastically, which isn't always true.

This paper aims to develop an algorithm that can effectively handle all these challenges simultaneously, minimizing the "regret" – the difference between the algorithm's performance and the best possible performance if it knew the future.

Methods

The core of the proposed solution, TV-HSGT, lies in a clever combination of techniques:

  • Hybrid Stochastic Gradient Tracking: This is the main innovation. It combines two strategies to reduce the impact of noisy gradients:
  • Variance Reduction: By blending current and recursively computed stochastic gradients, it smooths out noise.
  • Gradient Tracking: Agents communicate to estimate the overall "descent direction" of the global objective function, even with local information.
  • Time-Varying Directed Networks: The algorithm is designed to work with networks where communication links can change direction and strength over time. It uses "row-stochastic" and "column-stochastic" communication schemes, which are more flexible than traditional methods and avoid the need to estimate complex network properties like Perron vectors.
  • Adapt-Then-Combine (ATC) Framework: This framework allows for more flexible step-size choices compared to "Combine-Then-Adapt" methods, contributing to better performance.

Datasets

The paper evaluates the proposed algorithm on two standard datasets for distributed logistic regression:

  • A9A dataset: A structured dataset.
  • MNIST dataset: An image dataset for multi-class classification.

No new datasets were introduced.

Key Insights and Ideas

  • Hybrid variance reduction is key: The paper demonstrates that combining current and recursive gradients is more effective than using either alone for handling noisy, dynamic data.
  • Flexibility in directed networks: The use of row- and column-stochastic matrices allows the algorithm to adapt to more realistic, asymmetric communication patterns without complex network analysis.
  • ATC framework benefits: The choice of the ATC framework contributes to the algorithm's robustness and ability to handle dynamic settings.
  • No bounded gradient assumption: This is a significant theoretical advantage, making the algorithm applicable to a wider range of real-world problems where gradients can be large or change rapidly.

Key Results

  • Improved Dynamic Regret: Theoretical analysis shows that TV-HSGT achieves improved bounds on dynamic regret, meaning it performs closer to the optimal solution over time, even with changing objectives.
  • Experimental Validation: Simulations on A9A and MNIST datasets show that TV-HSGT consistently outperforms baseline methods (DSGD, DSGT, DSGT-HB) in terms of regret, loss, and accuracy.
  • Effect of Mixing Parameter (β): Experiments reveal that smaller values of the mixing parameter β (controlling the balance between current and recursive gradients) generally lead to better performance, confirming the theoretical insights on variance reduction.
  • Sublinear Convergence: The algorithm is shown to achieve sublinear convergence for dynamic regret, a desirable property for online learning algorithms.

Limitations and Future Work

  • Communication Efficiency: While the algorithm is effective, the paper suggests future work could focus on improving communication efficiency, as transmitting gradient information can still be a bottleneck.
  • Generalization to Non-convex Problems: The current theoretical analysis primarily focuses on convex or strongly convex objectives. Extending the framework to non-convex optimization problems would be a valuable next step.
  • Practical Implementation: While the paper addresses directed networks, further exploration into optimizing the communication schemes for specific network topologies could enhance practical deployment.

Summary updated

BibTeX
@misc{shi2025hybrid,
  author = {Xinli Shi and Xingxing Yuan and Longkang Zhu and Guanghui Wen},
  title = {{A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks}},
  year = {2025},
  eprint = {2508.20645},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.20645},
}
Figure