Pith. sign in

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 →

arxiv 2411.16477 v1 pith:ZKATXFWZ submitted 2024-11-25 cs.LG

classification cs.LG MSC 68W2790C25
keywords distributedonlineoptimizationnetworkregretstochasticclientavailabilitygossipalgorithmsfollow-the-regularized-leaderconvexlearningspectralgapintermittentparticipation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether distributed online learning is still controllable when clients are not always available. It studies a protocol where each agent is active with probability p at every round, and communication is only possible between simultaneously active neighbors. The paper introduces Gossip-FTRL, in which each active agent runs FTRL on a gossip-averaged estimate of the cumulative gradient, and proves that the expected network regret—the average regret over active agents—is O((κ(G)/p) min{√N, $N^{{1/4}}$/√p} √T) in the uniform-activation case, where κ(G) is the condition number of the graph Laplacian. This shows that random availability costs roughly a 1/p factor, but the √T scaling of single-agent online learning survives. The paper also proves a lower bound at p=1 showing that the average-over-agents regret is essentially as hard as the standard worst-case regret, so the averaging notion is not a way to avoid the difficulty.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [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.
  2. [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.
  3. [Section 4, after Eq. (6)] The phrase 'one can can set' contains a duplicated word and should read 'one can set'.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 4 assumptions · 0 invented entities

The results are analytic; no data fitting. The only hand-chosen quantities are the learning rate and gossip weight, both set by closed-form formulas. The main load-bearing assumptions are the i.i.d. activation model, connected graph, and standard convexity/Lipschitz conditions.

free parameters (2)
  • learning rate η = (D/L)√μ/2 sqrt(2p/(min(pN,√N)T))
    Set analytically to balance the FTRL regret and gossip error terms in Theorem 1; not fitted to data, but the bound depends on this choice.
  • gossip weight b = 1/λ1(G)
    Chosen as the largest step size that keeps W_t = I − b Lap(G_t) nonnegative and doubly stochastic; affects the spectral gap ρ in Theorem 5 and Corollary 1.
assumptions (4)
  • domain assumption Losses are convex and L-Lipschitz on a convex closed domain X, and the regularizer ψ is µ-strongly convex.
    Standard FTRL assumptions stated in Section 2; used in the omniscient-agent regret bound and the duality argument (Eq. 21).
  • domain assumption Activation indicators are independent across agents and time, with fixed probabilities p_v and Σ p_v ≥ 1.
    Makes the gossip matrices i.i.d. and ensures a non-negligible number of active steps; Lemma 2 and Theorem 1 rely on this.
  • 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.
    Required for the contraction product bound in Lemma 2 and the positive spectral gap 1−ρ; if G is disconnected, the regret bound is void.
  • domain assumption The activation probability p (or p_min) is known for tuning the learning rate.
    The learning-rate formulas in Theorem 1 and Corollaries use p or p_min; the paper lists the unknown-p case as an open problem.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2411.16477 by the authors.

Figure 1
Figure 1. Empirical estimate ˆρ compared to ρ and the upper bound ˆρup (10) for b = 1/λ1(G) plotted as a function of p ∈ [0, 1]. Note that 1−cos(π/M) 2−2 cos(π(M−1)/M) ∼ π 2 4M2 , which goes to zero when M → ∞ [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 3
Figure 3. Network regret of Gossip-FTRL and DOGD after T = 1000 steps on a grid with N = 36. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 p 0.06 0.07 0.08 0.09 0.10 0.11 0.12 0.13 0.14 1 √ Rnet T Gossip-FTRL DOGD [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Plot of Rnet T −1/2 for Gossip-FTRL on a clique for p ∈ [0, 1] and T = 1000. 1 2 3 4 5 6 7 8 9 10 Number of edges 100 120 140 160 180 200 220 Rnet T Gossip-FTRL [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figures from the paper (1 more)
Figure 5
Figure 5. Figure 5: Network regret of Gossip-FTRL after T = 1000 steps when p = 0.5, q = 1, and G is made up by two cliques joined by a varying number of random edges [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [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

  2. [2]

    B., and Pati, S

    Barik, S., Bapat, R. B., and Pati, S. (2015). On the laplacian spectra of product graphs. Applicable Analysis and Discrete Mathematics , pages 39--58

  3. [3]

    Bertsekas, D. P. and Tsitsiklis, J. N. (1991). Some aspects of parallel and distributed iterative algorithms—a survey. Automatica , 27(1):3--21

  4. [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

  5. [5]

    Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. (2006). Randomized gossip algorithms. IEEE transactions on information theory , 52(6):2508--2530

  6. [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

  7. [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

  8. [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

Show all 28 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [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

  8. [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

  9. [17]

    Orabona, F. (2019). A modern introduction to online learning. arXiv preprint arXiv:1912.13213

  10. [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

  11. [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

  12. [20]

    Spielman, D. (2019). Spectral and algebraic graph theory. Yale lecture notes, draft of December , 4:47

  13. [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

  14. [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

  15. [23]

    and Boyd, S

    Xiao, L. and Boyd, S. P. (2004). Fast linear iterations for distributed averaging. Syst. Control. Lett. , 53(1):65--78

  16. [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

  17. [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

  18. [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

  19. [27]

    Yuan, D., Proutiere, A., and Shi, G. (2020). Distributed online linear regressions. IEEE Transactions on Information Theory , 67(1):616--639

  20. [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

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.