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

Xinli Shi, Xingxing Yuan, Longkang Zhu, Guanghui Wen · 2025

Read A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks by Xinli Shi, Xingxing Yuan, Longkang Zhu, Guanghui Wen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20645.txt.

Introduction

Xinli Shi, Xingxing Yuan, Longkang Zhu, and Guanghui Wen wrote a 2025 paper on a learning rule for teams of agents that must choose good actions live, as the ground shifts. Each agent sees part of the world. The team must act as one, yet its links form a one-way network that changes with time. Old rules lean on a tame slope assumption and overlook the noise in the grade of each action.

The new rule mixes two gradient tracks: the fresh gradient and a recursive track that calms noise. It communicates both ways down the ranks of the network: rows out, columns in, in a blend. That blend removes the need to know the core weights of the network. Proofs give a tight bound on the lag of the team against the best later actions, with no tame slope assumption. Tests on a known task support the gains.

Catalog record

CREATORXinli Shi, Xingxing Yuan, Longkang Zhu, Guanghui Wen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20645

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks Xinli Shi, Xingxing Yuan, Longkang Zhu, Guanghui Wen Abstract 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. keywords distributed online optimization; hybrid stochastic gradient tracking; time-varying directed networks; dynamic regret , , , 1 Introduction Distributed optimization has received significant attention and found applications in various fields such as control, signal processing, and machine learning shahrampour2015distributed ; nedic2017fast ; Shahrampour2017ACC . It aims to solve a large-scale optimization problem by decomposing it into smaller, more tractable subproblems that can be solved iteratively and in parallel by a network of interconnected agents through communication. Most traditional works on distributed optimization focus on static problems, making them unsuitable for dynamic tasks arising in real-world applications, such as networked autonomous vehicles, smart grids, and online machine learning, among others Dall2020 . Online optimization, which addresses time-varying cost functions, plays a vital role in solving dynamic problems in timely application fields Zinkevich2003 ; Mairal2009 ; Li2024TAC ; Cao2021TAC . In many practical scenarios, such as machine learning with information streams shalev2012online , the objective functions of optimization problems change over time, making them inherently dynamic wei2023distributed ; Zinkevich2003 . Online learning has emerged as a powerful method for handling sequential decision-making tasks in dynamic contexts, enabling real-time operation while ensuring bounded performance loss in terms of regret hazan2016introduction . Regret is the gap between the cumulative objective value achieved by the online algorithm and that of the optimal offline solution li2020distributed ; Shahrampour2018 . In the literature, two types of regret are commonly considered, i.e., static and dynamic regret . The former evaluates the performance of an online algorithm relative to a fixed optimal decision x^{*} , and is typically formulated as \min_{t=1}^{T}(f_{t}(x_{t})-f_{t}(x^{*})) , where x_{t} denotes the output of the online algorithm and x^{*} is the optimal fixed decision in hindsight, i.e., x^{*}\in\arg\min_{t=1}^{T}f_{t}(x) . In contrast, the dynamic regret is obtained by replacing the above static x^{*} by a dynamic solution x_{t}^{*}\in\arg\min f_{t}(x) . This makes dynamic regret more suitable for non-stationary environments, although it is generally more challenging to minimize due to the evolving nature of the optimal points. Both metrics are commonly used to assess the performance of online algorithms. Achieving a sublinear regret growth, i.e., one that grows slower than linearly with time, is often regarded as a key indicator of algorithmic efficiency yuan2017adaptive . Therefore, minimizing regret, particularly in terms of establishing sublinear regret bounds, is fundamental to the design and analysis of effective online optimization methods. Table 1: Comparison with Distributed Online Optimization Algorithms Works Weight Matrix TVN? SG? NBG? Mo. Term? Regret Type Shahrampour2018 Undirected, DS ✗ ✓ ✗ ✗ Dynamic cao2023decentralized Undirected, DS ✗ ✗ ✗ ✗ Static Zhang2022SMC Directed, DS ✓ ✗ ✗ ✗ Static nazari2022dadam Undirected, DS ✗ ✓ ✗ ✓ Dynamic Li2022TCMS Directed, DS ✓ ✓ ✗ ✗ Dynamic carnevale2022gtadam Undirected, DS ✗ ✗ ✓ ✓ Dynamic Sharma2024TSP Undirected, DS ✗ ✗ ✓ ✗ Dynamic Li2024TAC Directed, RS ✗ ✓ ✗ ✗ Static yao2025online Directed, RCS ✗ ✗ ✗ ✗ Dynamic Ours Directed, RCS ✓ ✓ ✓ ✓ Dynamic Note: “TVN?” indicates whether the network is time-varying; “SG?” indicates whether stochastic gradients are used; “NBG?” means no bounded gradient assumption in the analysis; “Mo. Term?” indicates whether momentum terms are incorporated in the algorithm; “RCS” stands for row- and column-stochastic weight matrices; “RS” and “DS” denote row-stochastic and doubly stochastic weight matrices, respectively; “Mo.” is short for momentum. Distributed online optimization offers a flexible framework for handling dynamic settings, combining the benefits of decentralized computation with the ability to adapt to non-stationary environments. Earlier works hosseini2013online ; yan2012distributed investigate online distributed optimization in networks with doubly stochastic mixing matrices and achieve a static regret bound of \mathcal{O}(\sqrt{T}) . Shahrampour2018 further consider dynamic regret for both determined and stochastic online distributed optimization. carnevale2022gtadam propose GTAdam without the bounded gradient assumption, combining gradient tracking and adaptive momentum. However, these works assume static or undirected communication topologies, which are insufficient for modeling dynamic networked systems with directional and time-varying interactions. To address this, several algorithms have been developed under time-varying directed graphs with corresponding theoretical guarantees. For instance, Lee2018TCNS propose the ODA-PS algorithm by integrating dual averaging with the Push-Sum protocol over a directed time-varying network, achieving an \mathcal{O}(\sqrt{T}) static regret. Li2021TAC further extend the Push-Sum framework to handle inequality-constrained optimization over unbalanced networks, establishing sublinear dynamic regret and constraint violation. Xiong2024TNSE address feedback delays and propose an event-triggered online mirror descent method with regret guarantees. In addition, stochastic gradient methods have been explored to reduce computational costs. Lee2017TAC analyze stochastic dual averaging under gradient noise, while Li2022TCMS introduce a gradient tracking scheme with aggregation variables, achieving regret bounds under both exact and noisy gradients. Nevertheless, many of the above methods rely on the assumption of uniformly bounded gradients and neglect the high variance commonly encountered in practice. Moreover, few of them nazari2022dadam ; Lee2017TAC ; Li2022TCMS ; Li2024TAC incorporate variance reduction techniques, limiting both accuracy and stability in stochastic settings. To overcome these limitations, recent studies have focused on gradient tracking-based approaches, which aim to approximate global descent directions by dynamically aggregating local gradient information. Zhang2019CDC establish dynamic regret bounds for a basic tracking scheme, while carnevale2022gtadam propose a momentum-enhanced variant inspired by adaptive methods. Sharma2024TSP develop a generalized framework for strongly convex objectives without requiring gradient boundedness, further advancing the applicability of gradient tracking in decentralized online settings. This work addresses the distributed online stochastic optimization over time-varying directed networks under limited computational resources, where agents interact over asymmetric communication links modeled by time-varying row- and column-stochastic mixing matrices. To overcome the challenges introduced by stochastic gradient noise and dynamic topologies, we design a novel online algorithm that incorporates hybrid variance reduction, gradient tracking, and an AB communication scheme Saadatniaki2020TAC ; Pu2021TAC ; Nguyen2023 . Table 1 summarizes the comparison of our methods with several existing online optimization algorithms in terms of communication schemes, gradient assumptions, and types of regret. The main contributions are summarized as follows: 1. We propose a Time-Varying Hybrid Stochastic Gradient Tracking method, named by TV-HSGT, for distributed online optimization over dynamic directed networks. It integrates a hybrid variance reduction strategy by combining current and recursive stochastic gradients. This method effectively reduces the variance introduced by stochastic gradients and accelerates convergence, as demonstrated in our experimental results. 2. To address the limited information access inherent in decentralized systems, the

Read the complete text