REVIEW 4 major objections 5 minor 28 references
Distributed Online Optimization with Stochastic Agent Availability
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Stochastic agent availability can be absorbed into the spectral gap of gossip averaging, leaving a √T network regret bound for distributed online optimization.
desk verdict First clean analysis of stochastic node availability in distributed online optimization, but Corollary 1's κ/p bound is a factor 1/p too optimistic; the abstract's κ/p² is the correct statement. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the random gossip matrix W_t = I - b Lap(G_t), where G_t is the graph induced by the active agents and b ≤ 1/λ1(G) makes the matrix doubly stochastic and nonnegative. Its expected second eigenvalue ρ² = λ2(E[W_1 W_1^T]) is the contraction factor for the deviations between local cumulative-gradient estimates z_t(v) and the omniscient average; Lemma 2 bounds E∥W_t ... W_{s+1} e_v - 1/N∥² by $ρ^{{2(t-s)}}$. Around this, the proof uses an omniscient FTRL agent to decompose the regret, the duality between strong convexity of the regularizer and smoothness of the conjugate to convert gradient deviations into prediction deviations, and Theorems 4 and 5 to express ρ through the Fiedler value and condition number κ(G) of the Laplacian.
What would settle it
Run Gossip-FTRL on a graph where the same agents tend to be inactive in back-to-back rounds (for example, diurnal availability) with the learning rate tuned as if activations were independent, and measure the network regret over T steps; if the regret grows faster than √T, the independence assumption is doing the work. Alternatively, on a cycle, simulate the i.i.d. activation model and check empirically that E∥W_t ... W_{s+1} e_v - 1/N∥² decays at rate $ρ^{{2(t-s)}}$; a slower decay would break Lemma 2 and the upper bound.
Extended reading notes
Core claim
The central discovery is that stochastic node availability can be absorbed into the spectral-gap analysis of gossip averaging. At each round the active agents induce a random graph, and the gossip matrix W_t = I - b Lap(G_t) is doubly stochastic; the quantity ρ = $\sqrt$(λ2(E[W_1 W_1^T])) controls how fast information propagates through the network. The authors prove that, for any connected graph, an omniscient FTRL agent provides a benchmark such that each agent's deviation from the omniscient prediction contracts at rate $ρ^{{t-s}}$, yielding expected network regret of order (1/(1-ρ)) min{√N, $N^{{1/4}}$/√p} √T in the p-uniform case, and O(κ(G)/p min{√N, $N^{{1/4}}$/√p} √T) after expressing ρ through the Laplacian condition number. A complementary lower bound at p=1 shows that any distributed online algorithm must suffer network regret Ω((ρ/(1-ρ))^{α/4} $N^{{(1-α)/2}}$ √T) on some graph, meaning the average over agents does not make the problem fundamentally easier than worst-case regret.
Load-bearing premise
The argument requires that agents' activation events are independent across agents and time with a known probability, so that the gossip matrices are i.i.d. and the spectral-gap contraction lemma applies; if availability is correlated over time or the probability is unknown, the stated bounds and learning-rate tuning no longer follow.
Editorial extensions
If this is right
- In the p-uniform case, the expected network regret of Gossip-FTRL is O((κ(G)/p) min{√N, N^{1/4}/√p} √T), so random availability worsens regret only by roughly a 1/p factor while preserving the √T rate.
- At p=1, the lower bound Ω((ρ/(1-ρ))^{α/4} N^{(1-α)/2} √T) shows that the average-over-active-agents regret is essentially as hard as the standard worst-case regret, so averaging over agents does not sidestep the difficulty.
- The Erdős-Rényi random-edge setting is recovered as a special case, with expected regret O(κ(G)/(pq) min{√N, N^{1/4}/√p} √T) when each edge is active with probability q.
- A high-probability version of the bound holds with probability 1-δ and only logarithmic dependence on 1/δ, at the cost of an extra polynomial-in-N factor that disappears when agents know |S_t|.
- For dense graphs such as cliques the spectral gap makes ρ=0, giving an expected regret of order √T that does not grow with N.
Reading between the lines
- If p is not known in advance, an adaptive learning-rate schedule could in principle preserve the √T guarantee; the current analysis requires p (or bounds pmin, pmax) for tuning.
- Because the global loss is an average over active agents, the setting maps directly onto federated learning with client subsampling, so one testable extension is to compare Gossip-FTRL's communication protocol with standard partial-participation schedules on real non-i.i.d. data.
- Time-correlated availability (for example diurnal client cycles) breaks the i.i.d. gossip-matrix assumption; a natural extension would replace the constant spectral gap ρ with a mixing-time-based contraction and would likely pay an extra factor depending on the correlation length.
- The lower-bound construction uses a cycle, so topology bottlenecks appear to drive the price of intermittency; adding edges to a bottleneck should reduce regret, consistent with the paper's Figure 5.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies distributed online convex optimization with stochastic agent availability: at each round each agent is active with probability p_v, inactive agents neither incur loss nor communicate. The authors propose Gossip-FTRL, a distributed FTRL variant with gossip-based gradient averaging, and analyze its expected and high-probability network regret, defined as the average over active agents of instantaneous regret. The main claims are an expected regret bound depending on the spectral gap of the expected gossip matrix (Theorem 1), a p-uniform rate stated as O(κ/p min{√N, N^{1/4}/√p}√T) (Corollary 1), a high-probability bound (Theorem 2), and a lower bound for p=1 showing the average-agent network regret is essentially as hard as worst-agent regret (Theorem 3). The paper also gives closed-form spectral-gap computations for cliques, strongly regular graphs, grids, and random edge-deletion, plus synthetic experiments comparing Gossip-FTRL with DOGD.
Significance. If the quantitative claims are corrected, this is a solid contribution: it is, to my knowledge, the first DOO analysis with stochastic node availability, it recovers existing edge-availability bounds as a special case, and it provides a self-contained FTRL/gossip analysis with explicit learning-rate and gossip-weight formulas rather than fitted parameters. The appendix contains detailed proofs, the spectral computations in Section 6 are explicit, and the experiments are reproducible in principle. The lower bound at p=1 is valuable because it connects the average-agent network regret to the standard worst-agent regret. The main weakness is that several formal statements overstate what the proofs establish, most importantly the p-dependence in Corollaries 1 and 2; these issues are local and fixable, but they are load-bearing.
major comments (4)
- [Corollary 1, Eq. (14); Corollary 2, Eq. (15)] The advertised rate in Corollary 1, E[Rnet_T] = O((κ(G)/p) min{√N, N^{1/4}/√p}√T), does not follow from Theorem 1 and Lemma 4. Lemma 4 gives ρ/(1−ρ) ≤ 2κ(G)/p², hence 1/(1−ρ) ≤ 1+2κ/p² ≤ 3κ/p² for κ≥1; substituting into the optimized bound (6) yields O((κ(G)/p²) min{√N, N^{1/4}/√p}√T), which is the abstract's rate, not the κ/p rate of Eq. (14). This is not a loose-constant artifact: for a cycle or path, 1−ρ = Θ(p²/κ), so 1/(1−ρ) = Θ(κ/p²), and the claimed κ/p bound is a factor p too optimistic in the small-p regime. Corollary 2 has the same issue: with edge-activation probability q, the same derivation gives κ/(p²q²), not κ/(pq). Please correct these statements or provide a genuinely new argument for the stronger contraction.
- [Theorem 1, Eq. (6)] The displayed learning rate in Theorem 1, η = (D/L)√μ/2 · √(2p min(pN,√N)T), scales as √T, which is not the correct FTRL tuning for a finite-horizon bound. Substituting this η into Eq. (5) makes the two terms scale as T^{3/2} and 1/√T, so the stated regret bound (6) does not follow. The bound (6) appears to require the reciprocal scaling η = (D/L)√μ / (2√(2p min(pN,√N)T)). Please correct the displayed formula and re-derive the resulting constants.
- [Appendix E, proof of Theorem 3] The lower-bound proof is internally inconsistent. The network loss is defined as ℓnet_t(V,x) = M(N−M+1)/N H_k(x), but the regret computation pulls out only (N−M+1)/N, dropping the factor M; carrying the M through changes the displayed bound by a factor M. In addition, the nonzero local losses are (N−M+1)H_k, whose Lipschitz constant is (N−M+1)L, not L, so the constructed losses do not satisfy the theorem's L-Lipschitz hypothesis. Finally, the transition from per-agent regret to network regret uses 1/N ∑_{v∈U} but does not multiply by |U|=M. The qualitative Θ(√N√T) lower bound may survive after rescaling the local losses and accounting for the averaging over agents, but the proof as written requires a substantial correction.
- [Section 6, proof of Theorem 4] The proof of Theorem 4 asserts λ2(E[W1]) ≤ λ2(I − b P Lap(G)P). This inequality is false for non-uniform activation probabilities: for N=2, p1=0.1, p2=0.9, and b=1/λ1(G)=1/2, λ2(E[W1])=0.91 while λ2(I−b P Lap(G)P)=0.59. The claimed final bound ρ² ≤ 1−b p²_min λ_{N−1}(G) is nevertheless true and follows directly from x^T E[Lap(G1)]x = ∑_{(i,j)∈E} p_i p_j (x_i−x_j)^2 ≥ p²_min x^T Lap(G)x. Since Theorem 4 is used for the arbitrary-probability bound (7), please repair the proof rather than relying on the current chain of inequalities.
minor comments (5)
- [Section 2 vs. Section 3] The introduction says activation probabilities are unknown, while the algorithm and tuning require p (or p_min) to be known; please clarify exactly which quantities must be known for each bound.
- [Appendix E, proof of Theorem 3] The statement 'λ1(G)=1' for the cycle Laplacian is incorrect for the unnormalized Laplacian; the largest eigenvalue is 2−2cos(2π⌊N/2⌋/N), which is about 4 for large N. The subsequent bound still holds with the correct value, but the text should be corrected.
- [Section 4, after Eq. (6)] The phrase 'one can can set' contains a duplicated word and should read 'one can set'.
- [Theorem 2] The high-probability bound as stated has a constant 3 inside the parentheses, while the final line of its proof, Eq. (28), has a 4; please align the constants.
- [Figure 1 caption] The caption says 'The quantity bρ2 is the second eigenvalue of W1²...' which appears to contain a typo; the intended quantity is likely the empirical estimate ρ̂². Please clarify.
Circularity Check
No significant circularity: the regret bounds are derived from stated assumptions using standard FTRL and gossip analysis, and the only self-citation is not load-bearing.
full rationale
I walked the derivation chain. Theorem 1 decomposes the network regret with an omniscient-agent argument (Lemma 1), bounds the omniscient term using standard single-agent FTRL analysis, and bounds the deviation term using the gossip contraction Lemma 2, whose proof is included. Theorem 4 and Theorem 5 bound the spectral quantity rho using Laplacian eigenvalues and the stated gossip-matrix construction, and Corollary 1 substitutes these bounds into Theorem 1. All tunable parameters (learning rate eta and gossip weight b) are fixed closed-form functions of p, N, T, and lambda_1(G); no parameter is fitted to regret data. The only self-citation, Cesa-Bianchi et al. (2020) in Remark 2, is explicitly comparative and non-load-bearing: the paper states that the single-task setting is not comparable to DOO, so the citation does not supply any ingredient of the proof. The known-|S_t| variant and the nonstationary activation extension are presented with their own assumptions and proofs rather than assumed into the main bound. The internal mismatch between the O(kappa/p) claim in Corollary 1 and the O(kappa/p^2) bound that follows from Lemma 4 is a mathematical consistency concern, not a circularity concern: it would be an algebra or substitution error between independently derived results, not a definitional identity or a fitted parameter renamed as a prediction. The lower bound in Theorem 3 adapts an external result (Wang and Ji 2022) and is proved in the appendix. I therefore find no step where a claimed prediction or first-principles result reduces by construction to its own input.
Assumptions & free parameters
free parameters (2)
- learning rate η =
(D/L)√μ/2 sqrt(2p/(min(pN,√N)T))
- gossip weight b =
1/λ1(G)
assumptions (4)
- domain assumption Losses are convex and L-Lipschitz on a convex closed domain X, and the regularizer ψ is µ-strongly convex.
- domain assumption Activation indicators are independent across agents and time, with fixed probabilities p_v and Σ p_v ≥ 1.
- domain assumption The communication graph G is connected, and the gossip matrix W_t is doubly stochastic with W_t(v,·) = e_v for inactive agents.
- domain assumption The activation probability p (or p_min) is known for tuning the learning rate.
Cite this review
Pith. "Pith review of Distributed Online Optimization with Stochastic Agent Availability." pith.science (2026). https://pith.science/paper/ZKATXFWZ
@misc{pith2026241116477,
author = {Pith},
title = {Pith review of: Distributed Online Optimization with Stochastic Agent Availability},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZKATXFWZ}},
note = {Machine review of arXiv:2411.16477}
}
abstract
Motivated by practical federated learning settings where clients may not be always available, we investigate a variant of distributed online optimization where agents are active with a known probability $p$ at each time step, and communication between neighboring agents can only take place if they are both active. We introduce a distributed variant of the FTRL algorithm and analyze its network regret, defined through the average of the instantaneous regret of the active agents. Our analysis shows that, for any connected communication graph $G$ over $N$ agents, the expected network regret of our FTRL variant after $T$ steps is at most of order $(\kappa/p^2)\min\big\{\sqrt{N},N^{1/4}/\sqrt{p}\big\}\sqrt{T}$, where $\kappa$ is the condition number of the Laplacian of $G$. We then show that similar regret bounds also hold with high probability. Moreover, we show that our notion of regret (average-case over the agents) is essentially equivalent to the standard notion of regret (worst-case over agents), implying that our bounds are not significantly improvable when $p=1$. Our theoretical results are supported by experiments on synthetic datasets.
Figures
Reference graph
Works this paper leans on
-
[1]
M., G \"u nd \"u z, D., Kulkarni, S
Amiri, M. M., G \"u nd \"u z, D., Kulkarni, S. R., and Poor, H. V. (2021). Convergence of update aware device scheduling for federated learning at the wireless edge. IEEE Transactions on Wireless Communications , 20(6):3643--3658
work page 2021
-
[2]
Barik, S., Bapat, R. B., and Pati, S. (2015). On the laplacian spectra of product graphs. Applicable Analysis and Discrete Mathematics , pages 39--58
work page 2015
-
[3]
Bertsekas, D. P. and Tsitsiklis, J. N. (1991). Some aspects of parallel and distributed iterative algorithms—a survey. Automatica , 27(1):3--21
work page 1991
-
[4]
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. (2005). Gossip algorithms: Design, analysis and applications. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. , volume 3, pages 1653--1664. IEEE
work page 2005
-
[5]
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. (2006). Randomized gossip algorithms. IEEE transactions on information theory , 52(6):2508--2530
work page 2006
-
[6]
Cesa-Bianchi, N., Cesari, T., and Monteleoni, C. (2020). Cooperative online learning: Keeping your neighbors updated. In Algorithmic learning theory , pages 234--250. PMLR
work page 2020
-
[7]
C., Agarwal, A., and Wainwright, M
Duchi, J. C., Agarwal, A., and Wainwright, M. J. (2011). Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control , 57(3):592--606
work page 2011
-
[8]
Eichner, H., Koren, T., McMahan, B., Srebro, N., and Talwar, K. (2019). Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning , pages 1764--1773. PMLR
work page 2019
Show all 28 references
-
[9]
Gu, X., Huang, K., Zhang, J., and Huang, L. (2021). Fast federated learning in the presence of arbitrary device unavailability. Advances in Neural Information Processing Systems , 34:12052--12064
2021
-
[10]
Hosseini, S., Chapman, A., and Mesbahi, M. (2013). Online distributed optimization via dual averaging. In 52nd IEEE Conference on Decision and Control , pages 1484--1489. IEEE
2013
-
[11]
Hosseini, S., Chapman, A., and Mesbahi, M. (2016). Online distributed convex optimization on dynamic networks. IEEE Transactions on Automatic Control , 61(11):3545--3550
2016
-
[12]
Lei, J., Yi, P., Hong, Y., Chen, J., and Shi, G. (2020). Online convex optimization over E rdos- R \'e nyi random networks. Advances in neural information processing systems , 33:15591--15601
2020
-
[13]
and Cort \'e s, J
Mateos-N \'u nez, D. and Cort \'e s, J. (2014). Distributed online convex optimization over jointly connected digraphs. IEEE Transactions on Network Science and Engineering , 1(1):23--37
2014
-
[14]
and Olshevsky, A
Nedi \'c , A. and Olshevsky, A. (2014). Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control , 60(3):601--615
2014
-
[15]
and Ozdaglar, A
Nedic, A. and Ozdaglar, A. (2009). Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control , 54(1):48--61
2009
-
[16]
Nedic, A., Ozdaglar, A., and Parrilo, P. A. (2010). Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control , 55(4):922--938
2010
-
[17]
Orabona, F. (2019). A modern introduction to online learning. arXiv preprint arXiv:1912.13213
2019 arXiv
-
[18]
Raginsky, M., Kiarashi, N., and Willett, R. (2011). Decentralized online convex programming with local information. In Proceedings of the 2011 American Control Conference , pages 5363--5369. IEEE
2011
-
[19]
and Shen, C
Shi, C. and Shen, C. (2021). Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 35, pages 9603--9611
2021
-
[20]
Spielman, D. (2019). Spectral and algebraic graph theory. Yale lecture notes, draft of December , 4:47
2019
-
[21]
Wan, Y., Wei, T., Song, M., and Zhang, L. (2024). Nearly optimal regret for decentralized online convex optimization. In Proceedings of Thirty Seventh Conference on Learning Theory , volume 247 of Proceedings of Machine Learning Research , pages 4862--4888. PMLR
2024
-
[22]
and Ji, M
Wang, S. and Ji, M. (2022). A unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems , 35:19124--19137
2022
-
[23]
and Boyd, S
Xiao, L. and Boyd, S. P. (2004). Fast linear iterations for distributed averaging. Syst. Control. Lett. , 53(1):65--78
2004
-
[24]
Yan, F., Sundaram, S., Vishwanathan, S., and Qi, Y. (2013). Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Data Engineering , 25(11):2483--2493
2013
-
[25]
Yan, Y., Niu, C., Ding, Y., Zheng, Z., Tang, S., Li, Q., Wu, F., Lyu, C., Feng, Y., and Chen, G. (2024). Federated optimization under intermittent client availability. INFORMS Journal on Computing , 36(1):185--202
2024
-
[26]
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., and Johansson, K. H. (2019). A survey of distributed optimization. Annual Reviews in Control , 47:278--305
2019
-
[27]
Yuan, D., Proutiere, A., and Shi, G. (2020). Distributed online linear regressions. IEEE Transactions on Information Theory , 67(1):616--639
2020
-
[28]
Yuan, D., Proutiere, A., and Shi, G. (2021). Distributed online optimization with long-term constraints. IEEE Transactions on Automatic Control , 67(3):1089--1104
2021
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.