- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies token-based Markov chain SGD when nodes are intermittently available for computation. It derives a convergence bound with an availability-induced bias term, proves an asymptotic lower bound for this term, and studies inverse-probability correction. Quadratic and neural-network experiments illustrate the bias and correction effects.
Critical strengths
- The period-wise analysis gives a convergence guarantee for unmodified Markov chain SGD without a burn-in requirement. This is a useful technical contribution beyond the availability setting.
- The upper and lower bounds characterize the worst-case bias through the discrepancy between the effective and target distributions. The quadratic experiments provide a controlled illustration.
Critical weaknesses
- The central bias mechanism follows from reweighting node contributions by their availability probabilities, and inverse-probability correction is a standard remedy. The bias lower bound uses i.i.d. sampling, so it does not establish an additional difficulty caused by Markov dependence. The main novelty therefore rests largely on the finite-time analysis.
- The claim that correction slows convergence is stronger than the evidence establishes. A worse upper bound does not prove an unavoidable slowdown, and all reported experiments use a rapidly mixing chain with persistence 0.1. They do not adequately test the interaction between availability and Markov dependence.
Questions for authors
- Is the correction penalty involving unavoidable, or could a sharper bound depend on an average of the inverse availability rates?
- Does the observed correction trade-off persist for slowly mixing chains and after matching effective step sizes between corrected and uncorrected runs?
2 comments
Response 12: factor
Is the correction penalty involving unavoidable, or could a sharper bound depend on an average of the inverse availability rates?
The upper bound (after correction) consists of two terms: the optimization term (the first) and the error term (the second). In the original version, appears in both terms. In the revised version, we derive an improved bound where is not needed in the error term. The still appears in the optimization term, and it is necessary. Details are as follows.
-
The error term does not require .
Convergence rates when Original version Improved version -
The is necessary for the step-size restriction. According to Corollary 1, the factor enters the optimization term through the restriction on the step size . The following two-node example shows that the step-size restriction is necessary.
Define . Consider two nodes with availability probabilities , where . Let and . The chain reaches stationarity in one transition. Hence and for every , while can grow arbitrarily large. Take and . Their stationary average is , and both local gradient deviations are bounded by . Start at , so . Since , the first corrected update gives with probability and otherwise. At , the stationarity measure in Theorem 1 is therefore exactly
=\frac{p}{2}\left(\frac{\gamma L\varsigma}{p}\right)^2 =\frac{\gamma^2L^2\varsigma^2}{2p}.$$ On this instance ($H=2$, $\tau_{\mathrm{mix}}=1$, $F_0=0$), the right-hand side bound in Theorem 1 reduces to $\mathcal{O}(\gamma L\varsigma^2)$. Then, $\frac{\gamma^2 L^2 \varsigma^2}{2p} = \mathcal{O}(\gamma L \varsigma^2)$ yields $\gamma L=\mathcal{O}(p)=\mathcal{O}(1/A_2)$. This step-size restriction accounts for the remaining factor $\max_s \frac{1}{p_{s}}$ in the optimization term.
Reponse 10: Novelty
We clarify the main novelty of this work.
Response 11: Slowly Mixing Chains
We use the ρ in 0.0,0.1,0.3,0.9,0.99 to study the effect of the mixing time. The observations are as follows:
The three findings (i) the availability bias, (ii) correction help eliminate bias, (iii) and correction trade-off, are also observed in these experiments.
One new observation is that slower mixing can narrow the performance gap between IA-0 and IA-3 after correction.
This is consistent with our convergence bound: when the mixing-time term (τmix) dominates the availability-dependent terms ( maxsps1 and ∑spsπ(s)), the bound becomes less sensitive to differences in node availability. O(TLF0(maxsps1+τmix)+(TLF0ς2(∑spsπ(s)+τmix))21)
[Table 1: The average error of quadratic functions over the last 50% training iterations and 10 random seeds. A large ρ means a slower mixing Markov chains.]
[Table 2: The average training loss of logistic regression on MNIST over the last 50% training iterations and 5 random seeds. A large ρ means a slower mixing Markov chains.]