Many networks of devices talk in one direction only. A drone can hear a neighbor it cannot answer, and a sensor can broadcast to a relay that cannot reply. Such networks are often not even strongly connected, meaning some nodes can never hear from others. Suppose we want these devices to jointly train one model on their pooled data. A part of the network that sends messages out but never receives any cannot learn about the rest of the data. The usual fix is to give a few devices, which we call leaders, an expensive link to a base station. The base station can cheaply broadcast back to everyone. This note asks a question that neither control theory nor decentralized optimization has answered: given a budget of $k$ such uplinks, which devices should get them so that stochastic training reaches the exact optimum in as few communication rounds as possible?
Our bet is that variance reduction is what makes this question sharp. Variance reduction is a family of stochastic-gradient methods whose gradient noise shrinks to zero at the optimum, so they converge at a fixed geometric rate. Plain stochastic training stalls at a noise floor, and that floor hides the effect of the network's shape. With variance reduction the network enters only through the rate constant, so leader choice becomes a clean, measurable multiplier on training cost. We propose to predict that multiplier with a random-walk score that can be computed in parallel, and to choose leaders by minimizing it.
Core Claim
Consider a directed network plus a base station that broadcasts to all nodes and receives only from a leader set $S$. For stochastic decentralized training to converge exactly, every node's gradient must reach some leader along a directed path. That holds if and only if $S$ contains a node in every sink component of the network, where a sink component is a cluster that nothing flows out of. This is the structural-accessibility condition of Actuator Placement for Structural Controllability beyond Strong Connectivity and towards Robustness, which requires an actuator in every source component, applied to the reversed graph. It is also the "one leader per disconnected part" condition of Structural Controllability of a Consensus Network With Multiple Leaders.
The structural condition is only necessary. Beyond it, we hypothesize that the number of rounds needed to reach accuracy $\epsilon$ is governed by how long gradient information takes to reach the leaders:
$$ T_\epsilon(S) \approx c\,\big(\kappa + H(S)\big)\log(1/\epsilon), \qquad H(S) = \frac{1}{m}\sum_{i=1}^{m} \mathbb{E}[\tau_i(S)], $$
In this expression, $m$ is the number of nodes, $\kappa$ is the condition number of the training loss, and $\tau_i(S)$ is the number of steps a random walk from node $i$ takes to first hit $S$ when it moves along the push (column-stochastic) mixing weights. The form is a conjecture. It is modeled on how Leader Selection for Minimizing Convergence Error in Leader-Follower Systems: A Supermodular Optimization Approach reduces consensus error to random walks that end at a virtual leader. Testing it is the core of the proposal.
Research Program
The algorithm draws on two existing methods. Push-Pull Gradient Methods for Distributed Optimization in Networks shows that exact optimization over digraphs does not need strong connectivity. It only needs a common root that gradients can be pushed to and decisions pulled from. However, it uses exact full gradients. Push-SAGA adds variance reduction and proves linear convergence over digraphs. However, it assumes strong connectivity and stores a per-sample gradient table of size $O(n_i d)$ at every node, where $n_i$ is the node's sample count and $d$ is the model dimension.
We combine them into a leader-rooted push-pull method, making three changes to Push-SAGA's setting:
- Rooted topology instead of strong connectivity. The base station is the common root. Leaders form its only incoming edges, and its broadcast forms its outgoing edges.
- No gradient table. In place of Push-SAGA's per-node table, we use a table-free, single-loop version of SVRG, a variance-reduction method that periodically anchors noisy steps with a full gradient. The anchor (full) gradient is aggregated through the leaders and rebroadcast.
- Asynchronous followers. Followers update without waiting for one another, while the anchor may be stale by a bounded amount. This is the regime where Asynchronous Distributed Optimization With Delay-free Parameters found fast nodes doing 1.46 times more local iterations, but that paper handled only undirected graphs and exact gradients.
The theory target has two parts. First, we want a linear-rate proof under the sink-component condition. Second, we want a rate constant written in terms of $H(S)$, or honest evidence that a different graph quantity is the right one.
Leader selection then becomes minimizing $H(S)$ subject to the sink-component constraint. Clark et al.'s greedy method needs a matrix inverse at every step, and Guo et al.'s look-ahead greedy took 84.7 seconds versus 1.3 seconds for plain greedy on a 25-node graph. Both are sequential bottlenecks. Hitting times, by contrast, can be estimated by many independent random walks run in parallel. The marginal value of adding a candidate leader can be read off those same walk samples: we record where each walk would have stopped earlier. Whether $H$ is supermodular (has diminishing returns) is checked, not assumed. If it is, greedy selection inherits the $(1-1/e)$ approximation guarantee Clark et al. prove for their objective.
Baselines
The naive reference points come first. One is each weakly connected piece training on its own data with no uplinks. The other is stochastic gradient push with decaying step sizes on the hub-augmented graph. Push-SAGA reports that such decaying-step push methods (SGP, SADDOPT) need far more epochs than variance-reduced ones, but no reported numeric result found on Lacuna for that gap.
The strongest optimization baseline is Push-SAGA itself, run on the same hub-augmented graph, which is strongly connected once the sink condition holds. It gets the same leader set, the same data split, and the same step-size tuning grid. We beat it if our method reaches the same suboptimality in fewer communication rounds or less wall-clock time without the gradient table. Matching it with less memory is the minimum acceptable outcome. Di-CS-SVRG is a second variance-reduced directed baseline. It reports reaching 90% accuracy on Stackoverflow logistic regression with fewer gradient computations than full-gradient methods, but no exact count is given in the file.
The strongest placement baselines are three. The first is random and highest-degree leaders. The second is Clark et al.'s exact-inverse greedy, which reports under one third the convergence error of random or degree-based choice with 5 leaders; we give it the same budget $k$. The third is the key ablation, structural-only placement, which puts one arbitrary leader in each sink component. That ablation isolates whether rate-aware placement matters beyond the necessary condition. A second ablation turns variance reduction off, to test the claim that topology effects only become visible without a noise floor.
Why not just…?
Why not just add enough links to make the network strongly connected and run Push-SAGA? This is the real threat. With a hub, our leader uplinks are a form of strong-connectivity augmentation, so at equal link budget the two coincide structurally. Our claim is therefore not that we need fewer links. It is that which nodes receive the links changes the rate substantially, and that a cheap score predicts this. Running Push-SAGA with our leaders versus random leaders at the same budget settles it. If the gap is small, the placement contribution fails and only the table-free, asynchronous algorithm remains.
Why not just pick high-degree or random leaders? Two reasons. Random choice can miss a sink component, and then the method provably never reaches the global optimum. And Clark et al. found that heuristics give three times the consensus error. Whether this carries over from consensus error to optimization rate is exactly what the structural-only and degree baselines measure.
Why not just use decentralized SGD with decaying step sizes? It avoids anchors and tables. However, its noise floor would mask placement effects, and Push-SAGA and ECL-ISVR both report that non-variance-reduced methods drift under non-uniform data across nodes. The variance-reduction-off ablation tests this directly.
Why not just treat it as federated learning through relays? That is a fair description of the semi-centralized end of this design, and we say so. The difference is that followers never contact the server. Relaying happens over one-way peer links whose shape we optimize.
Proposed Experiments
We evaluate on synthetic digraphs with several strongly connected components, including a 25-node, 5-component setting mirroring Guo et al. We add one-way random geometric "drone" graphs of 50 to 500 nodes in which transmission range varies across nodes. Training tasks are logistic regression on Covertype and Stackoverflow, and small networks on MNIST and CIFAR-10 with non-uniform data splits across nodes, matching the Push-SAGA and ECL-ISVR setups. Follower delays are drawn from heavy-tailed distributions like those in Wu et al., where delays reached 160 while 95% stayed under 40.
The metrics are:
- rounds and wall-clock time to reach a fixed suboptimality;
- final test accuracy;
- memory per node;
- leader-selection time.
The first decisive check is predictive. Across at least a hundred leader sets per graph, the rank correlation between $H(S)$ and measured rounds-to-$\epsilon$ should be strong under variance reduction and noticeably weaker without it. The second check is practical. On graphs with bottleneck components, greedy-on-$H$ placement should need at least 1.5 times fewer rounds than structural-only placement at equal $k$. That threshold is preregistered, not taken from prior work. It should also match exact-inverse greedy in quality while selecting leaders at least an order of magnitude faster on 500-node graphs. Failing the first check means the conjectured rate form is wrong, and the program falls back to searching for the right graph quantity.
References
- Actuator Placement for Structural Controllability beyond Strong Connectivity and towards Robustness
- Structural Controllability of a Consensus Network With Multiple Leaders
- Leader Selection for Minimizing Convergence Error in Leader-Follower Systems: A Supermodular Optimization Approach
- Push-Pull Gradient Methods for Distributed Optimization in Networks
- Push-SAGA: A Decentralized Stochastic Algorithm With Variance Reduction Over Directed Graphs
- Asynchronous Distributed Optimization With Delay-free Parameters
- Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization Over Time-Varying Directed Graphs
- Asynchronous Decentralized Optimization With Implicit Stochastic Variance Reduction