acceptodds
Under review as a conference paper at ICLR 2027

Understanding the Bias of Markov Chain SGD with Intermittent Node Availability

Abstract

This paper studies stochastic gradient descent when the sampling process follows a Markov chain (Markov chain SGD). Specifically, we consider a token-based setting for distributed learning, where a token carrying the shared model moves sequentially among the nodes according to a Markov chain, and the node holding the token performs one gradient update. In practical distributed systems, nodes may be intermittently unavailable because of resource constraints. We analyze the convergence of Markov chain SGD with intermittent node availability. The derived upper and lower bounds of convergence rates show that different node availability rates can cause a non-vanishing optimization bias with respect to the intended objective, and that correction weights can correct for the bias at the cost of slower convergence. Experiments on quadratic functions and neural networks support our theoretical findings.

Primary area:
optimization
Keywords:
Markov Chain SGD, federated learning, non-convex optimization, convergence analysis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rYcpOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. Is the correction penalty involving 1/pmin⁡1/p_{\min} unavoidable, or could a sharper bound depend on an average of the inverse availability rates?
  2. Does the observed correction trade-off persist for slowly mixing chains and after matching effective step sizes between corrected and uncorrected runs?
2 comments

Reponse 10: Novelty

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.

We clarify the main novelty of this work.

  • New upper bound. We derive the upper bound of Markovian SGD without polylogarithmic factors, large-iteration condition and algorithmic modifications (Theorem 1).
  • New technique. We introduce the period (epoch)-wise analysis of permutation-based SGD (Koloskova et al., 2024) into the convergence analysis of Markovian SGD.
  • New setting. We study the token-based SGD with intermittent intermittent availability. The time-varying node availability makes the effective step size time-varying and makes the objective biased. This makes the analysis more challenging than vanilla Markovian SGD.
  • Rigorous characterization of the availability bias. Our bounds provide a rigorous characterization of the availability bias (Theorems 1 and 2), not only on developing a bias-correction algorithm. Based on them, we find some findings and then validate them by experiments.
  • Extension to Markovian availability (added during rebuttal). We relax the independence assumption by modeling the token location and node availability jointly as a Markov chain. Theorem 3 extends the convergence bound to this setting.

Response 11: Slowly Mixing Chains

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.

Does the observed correction trade-off persist for slowly mixing chains and after matching effective step sizes between corrected and uncorrected runs?

We use the ρ\rho in 0.0,0.1,0.3,0.9,0.99\\{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\widehat \tau_{\mathrm{mix}}) dominates the availability-dependent terms ( max⁡s1ps\max_{s} {\frac{1}{p^s}} and ∑sπ(s)ps\sum_{s}\frac{\pi(s)}{p^s}), the bound becomes less sensitive to differences in node availability. O(LF0(max⁡s1ps+τ^mix)T+(LF0ς2(∑sπ(s)ps+τ^mix)T)12)\mathcal{O}\left( \frac{ LF_0 \big({ \color{red}\max_{s} {\frac{1}{p^s}}} + {\color{blue}\widehat\tau_{\text{mix}}} \big) }{T} +\left(\frac{LF_0\varsigma^2\left({ \color{red}\sum_{s}\frac{\pi(s)}{p^s}}+{\color{blue}\widehat\tau_{\text{mix}}}\right)}{T} \right)^{\frac{1}{2}} \right)

[Table 1: The average error of quadratic functions over the last 50% training iterations and 10 random seeds. A large ρ\rho means a slower mixing Markov chains.]

ρ=0.0\rho=0.0FAIA-0IA-1IA-2IA-3
w/o correction0.02150.02910.59620.79570.8961
w/ correction0.02990.03270.04020.0500
ρ=0.1\rho=0.1FAIA-0IA-1IA-2IA-3
w/o correction0.02620.03050.59300.79820.9020
w/ correction0.03080.03860.04140.0596
ρ=0.3\rho=0.3FAIA-0IA-1IA-2IA-3
w/o correction0.02970.03960.59310.79100.8966
w/ correction0.03960.03820.04290.0673
ρ=0.9\rho=0.9FAIA-0IA-1IA-2IA-3
w/o correction0.05990.06180.54920.70050.8298
w/ correction0.05870.06470.06680.0693
ρ=0.99\rho=0.99FAIA-0IA-1IA-2IA-3
w/o correction0.22630.23680.56500.67250.7324
w/ correction0.22910.22680.23180.2427

[Table 2: The average training loss of logistic regression on MNIST over the last 50% training iterations and 5 random seeds. A large ρ\rho means a slower mixing Markov chains.]

ρ=0.0\rho=0.0FAIA-0IA-1IA-2IA-3
w/o correction0.29720.31720.36910.44000.5484
w/ correction0.31750.32570.34770.3786
ρ=0.1\rho=0.1FAIA-0IA-1IA-2IA-3
w/o correction0.30310.31990.37530.45840.6007
w/ correction0.32020.33180.35310.3975
ρ=0.3\rho=0.3FAIA-0IA-1IA-2IA-3
w/o correction0.31110.32650.37130.45460.5876
w/ correction0.32650.33010.35400.3845
ρ=0.9\rho=0.9FAIA-0IA-1IA-2IA-3
w/o correction0.43950.44370.50130.58340.7323
w/ correction0.44510.44260.44620.4613
ρ=0.99\rho=0.99FAIA-0IA-1IA-2IA-3
w/o correction0.98790.98291.07151.20391.3413
w/ correction0.98570.98500.99770.9822

Response 12: max⁡s1ps\max_s \frac{1}{p^s} factor

Is the correction penalty involving 1pmin\frac{1}{p_{min}} 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, max⁡s1ps\max_s \frac{1}{p^s} appears in both terms. In the revised version, we derive an improved bound where max⁡s1ps\max_s \frac{1}{p^s} is not needed in the error term. The max⁡s1ps\max_s \frac{1}{p^s} still appears in the optimization term, and it is necessary. Details are as follows.

  • The error term does not require max⁡s1ps\max_s \frac{1}{p^s}.

    Convergence rates when ws=1psw^s = \frac{1}{p^s}
    Original versionO(LF0(max⁡s1ps+τmix)T+(LF0ς2(max⁡s1ps+τmix)T)12)\mathcal{O}\left( \frac{ LF_0 \big( {\color{blue}\max_{s} {\frac{1}{p^s}}} + \tau_{\text{mix}} \big) }{T} +\left(\frac{LF_0 \varsigma^2\big( {\color{red}\max_{s} {\frac{1}{p^s}} } + \tau_{\text{mix}} \big) }{T} \right)^{\frac{1}{2}} \right)
    Improved versionO(LF0(max⁡s1ps+τ^mix)T+(LF0ς2(∑sπ(s)ps+τ^mix)T)12)\mathcal{O}\left( \frac{ LF_0 \big( {\color{blue}\max_{s} {\frac{1}{p^s}}} + \widehat\tau_{\text{mix}} \big) }{T} +\left(\frac{LF_0\varsigma^2\left({\color{red}\sum_{s}\frac{\pi(s)}{p^s}}+\widehat\tau_{\text{mix}}\right)}{T} \right)^{\frac{1}{2}} \right)
  • The max⁡s1ps\max_s \frac{1}{p^s} is necessary for the step-size restriction. According to Corollary 1, the factor A2=max⁡s1psA_2=\max_s \frac{1}{p^s} enters the optimization term through the restriction on the step size γL=O(1/A2)\gamma L =\mathcal{O}(1/A_2). The following two-node example shows that the step-size restriction γL=O(1/A2)\gamma L=\mathcal{O}(1/A_2) is necessary.

    Define H≔∑sπ(s)psH\coloneqq \sum_s \frac{\pi(s)}{p^s}. Consider two nodes with availability probabilities (p,1−p)(p,1-p), where 0<p≤120<p\leq \frac12. Let s0=1s_0=1 and M=(p1−pp1−p)M=\begin{pmatrix}p&1-p\\\\ p&1-p\end{pmatrix}. The chain reaches stationarity in one transition. Hence H=2H=2 and τmix=1\tau_{\mathrm{mix}}=1 for every pp, while A2=1/pA_2=1/p can grow arbitrarily large. Take f1(x)=12Lx2+ςxf_1(x)=\frac{1}{2}Lx^2+\varsigma x and f2(x)=12Lx2−(p/(1−p))ςxf_2(x)=\frac{1}{2}Lx^2-(p/(1-p))\varsigma x. Their stationary average is f(x)=12Lx2f(x)=\frac{1}{2}Lx^2, and both local gradient deviations are bounded by ς\varsigma. Start at x0=0x_0=0, so F0=0F_0=0. Since ∇f1(0)=ς\nabla f_1(0)=\varsigma, the first corrected update gives x1=−γς/px_1=-\gamma\varsigma/p with probability pp and x1=0x_1=0 otherwise. At T=2T=2, 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.
Reviewer_e3hzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies token-based Markov chain SGD in a distributed setting, where the node holding the token either performs a gradient update with probability ptsp_t^s and weight wtsw_t^s, or is unavailable but still forwards the token. The position of the token follows a Markov chain with stationary distribution π\pi.

Under smoothness and uniformly bounded gradient heterogeneity, Corollary 1 bounds a weighted average of expected squared gradient norms. This bound contains an optimization term decaying as 1/T1/T, a heterogeneity-noise term decaying as 1/T1/\sqrt T, and a non-vanishing bias term Φ2\Phi^2, with

\qquad \Phi = 2d_{TV}(\pi_{\mathrm{eff}},\pi)\varsigma,$$ where $\varsigma$ is a uniform heterogeneity bound. The upper-bounds hold for any time horizon and do not hide any poly-logarithmic terms. Theorem 2 provides a lower bound (using quadratic objectives and an i.i.d. chain) which is asymptotically proportional to $\Phi^2$, showing that this $\Phi^2$-term cannot be removed in general. Choosing $p^sw^s$ constant yields $\Phi^2 = 0$, at the cost of a $\max_s 1/p^s$ factor in the other terms. Experiments on a 1-D quadratic and on MNIST (logistic regression), CIFAR-10/100 (CNNs) illustrate the availability bias and its correction.
Critical strengths
  • The paper provides a clean convergence bound for Markovian SGD with intermittent availability. The period-wise analysis (Lemma 3) is an interesting transfer of the permutation-SGD technique of [1] to Markov sampling. When using p=w=1p=w=1, it yields a rate without log factors, and without explicit burn-in (that is, which holds for all values of TT), and without the randomized-batch modification of [2].

  • There is a clear and interpretable characterisation of the availability bias. The bias is expressed as $ \Phi = 2d_{TV}(\pi_{\mathrm{eff}},\pi)\varsigma ,withanexactzero−biascondition(, with an exact zero-bias condition (p^sw^s$ constant) and a matchinglower bound. The quadratic experiment keeps average availability fixed while varying the heterogeneity, and the experiments show that the weighting correction can improve performance and reduce the observed error.

Critical weaknesses
  • The paper has limited novelty.

Since δts\delta_t^s is independent of the past and E[δtswts∣st=s]=pswsE[\delta_t^sw_t^s\mid s_t=s]=p^sw^s, the algorithm is, in expectation, Markovian SGD on the reweighted objective feff=∑sπeff(s)fsf_{\mathrm{eff}}=\sum_s\pi_{\mathrm{eff}}(s)f_s. Since ∇f−∇feff=∑s(π(s)−πeff(s))(∇fs−∇f)\nabla f-\nabla f_{\mathrm{eff}}=\sum_s(\pi(s)-\pi_{\mathrm{eff}}(s))(\nabla f_s-\nabla f), one immediately has ∥∇f∥2≤2∥∇feff∥2+2Φ2\|\nabla f\|^2\le 2\|\nabla f_{\mathrm{eff}}\|^2+2\Phi^2, i.e. the Φ2\Phi^2 floor is some sort of "objective inconsistency" already seen in [3, 4, 5], and ws∝1/psw^s\propto1/p^s is the inverse-probability reweighting [5].

In particular, Theorem 1 of [5] states that, under Bernoulli participation with constant weights ωn\omega_n, FedAvg minimises h(x)∝∑nωnpnFn(x)h(x)\propto \sum_n\omega_np_nF_n(x), i.e. the analogous participation-weighted objective in the time-independent setting, with the same scale-free zero-bias condition (ωnpn\omega_np_n constant). The present paper transfers this message to token algorithms.

Theorem 2 establishes matching-order worst-case tightness of the bias term, but its i.i.d. construction does not establish tightness of the mixing-time dependence.

The conclusions of Section 3.3 (bias, and correction of this bias) therefore seem predictable from prior FL work.

The modelling assumptions are also rather simple: availability is independent over time (and i.i.d. in the setting of Corollary 1) and independent of the token's trajectory, probabilities ptsp_t^s are known and deterministic, and unavailable nodes still communicate. More interesting regimes for token algorithms (Markovian availability, availability depending on recent computation, etc.) are not covered.

  • Some claims are overstated, and the experiments do not stress the Markovian aspect.

No "large-iteration requirement" (Sec. 3.4): the first term LF0τmix/TLF_0\tau_{\mathrm{mix}}/T (with hidden constants of order 10710^7, as seen in the final inequality of App. A.3) is larger than LF0LF_0 unless T≳τmixT\gtrsim\tau_{\mathrm{mix}}. In [6] (v3 of the arXiv version), the burn-in is T≥2τmixln⁡τmixT\ge2\tau_{\mathrm{mix}}\ln\tau_{\mathrm{mix}}.

Heterogeneity measure: the bound uses ς2=max⁡sςs2\varsigma^2=\max_s\varsigma_s^2, which can be up to 1/min⁡sπ(s)1/\min_s\pi(s) times larger than ςπ2=Eπ[ςs2]\varsigma_\pi^2=E_\pi[\varsigma_s^2], the quantity used in [6]. This difference is acknowledged by the authors.

"nearly matching" the lower bound of [7] is not justified as stated: the lower bound of [7] is over chains with τhit≤c0τ\tau_{\mathrm{hit}}\le c_0\tau and with a variance bounded only on average under π\pi, which is a different class than the uniformly bounded heterogeneity assumed here (Assumption 3).

Experiments: the chain with ρ=0.1\rho=0.1 is nearly i.i.d. sampling: τmix=O(1)\tau_{\mathrm{mix}}=O(1) so τmix\tau_{\mathrm{mix}} is never varied. The experiments do not study the dependence on mixing or a more realistic graph random walk (as in Figure 1).

In the NN experiments, step sizes are tuned on the average training loss (Table 3). This makes it harder to actually visualize Finding 3. The uncorrected curves still seem to be decreasing for CIFAR, so it is hard to distinguish a non-vanishing plateau from slower convergence.

Questions for authors
  • Reduction. In the time-independent setting, the pair (st,δt)(s_t,\delta_t) is a Markov chain with stationary law π(s)Bern(ps)\pi(s)\mathrm{Bern}(p^s), and the expected update targets P feffP\,f_{\mathrm{eff}}. Combined with ∥∇f∥2≤2∥∇feff∥2+2Φ2\|\nabla f\|^2\le2\|\nabla f_{\mathrm{eff}}\|^2+2\Phi^2, which part of Theorem 1 cannot be obtained from an existing Markovian-SGD bound (e.g. using Assumption A4 in [2]) applied to this augmented chain? Please state what is technically new compared with this route.

  • Tightness of the cost of correction. Is the max⁡s1/ps\max_s1/p^s factor (in A2A_2) necessary for the unbiased weighting, or is it an artefact of the worst-case bound? In other words, do you have a lower bound for this term, or an experiment showing its effect?

  • Sharper bias term. Your proof of Lemma 3 (more precisely, the term T4\mathcal T_4) seems to give ∑s∣πeff(s)−π(s)∣ ςs\sum_s|\pi_{\mathrm{eff}}(s)-\pi(s)|\,\varsigma_s and a PtP_t-weighted average of ϕt2\phi_t^2 instead of sup⁡t\sup_t; could Theorem 1 be stated in this sharper form?

  • Experimental details. It would be useful to specify in the paper what step size and x0x_0 you use for the quadratic experiment; experiments with larger ρ\rho (slower mixing) and a random walk on a sparse graph would also be beneficial; for NNs, results at a common step size (not tuned on the configuration) would illustrate more clearly your findings.

References:

[1] A. Koloskova, N. Doikov, S. U. Stich, and M. Jaggi. On convergence of incremental gradient for non-convex smooth functions. In ICML, PMLR 235:25058--25086, 2024.

[2] A. Beznosikov, S. Samsonov, M. Sheshukova, A. Gasnikov, A. Naumov, and E. Moulines. First order methods with Markovian noise: from acceleration to variational inequalities. In NeurIPS 36, 2023. arXiv:2305.15938.

[3] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. In NeurIPS 33, pp. 7611-7623, 2020.

[4] Y. J. Cho, J. Wang, and G. Joshi. Towards understanding biased client selection in federated learning. In AISTATS, PMLR 151:10351--10375, 2022.

[5] S. Wang and M. Ji. A lightweight method for tackling unknown participation statistics in federated averaging. In ICLR, 2024. arXiv:2306.03401.

[6] M. Even. Stochastic gradient descent under Markovian sampling schemes. In ICML, PMLR 202:9412-9439, 2023. arXiv:2302.14428.

[7] Z. Sun and E. Wei. Learning from a single Markovian trajectory: optimality and variance reduction. In NeurIPS 38, 2025. doi:10.52202/085713-0675.

8 comments

Response 3: One reduction approach

Since is independent of This is similar to the past and E[δtswts∣st=s]=pswsE[\delta_t^sw_t^s\mid s_t=s]=p^sw^s, the algorithm is, in expectation, Markovian SGD on the reweighted objective feff=∑sπeff(s)fsf_{\mathrm{eff}}=\sum_s\pi_{\mathrm{eff}}(s)f_s. Since ∇f−∇feff=∑s(π(s)−πeff(s))(∇fs−∇f)\nabla f-\nabla f_{\mathrm{eff}}=\sum_s(\pi(s)-\pi_{\mathrm{eff}}(s))(\nabla f_s-\nabla f), one immediately has ∣∇f∣2≤2∣∇feff∣2+2Φ2|\nabla f|^2\le 2|\nabla f_{\mathrm{eff}}|^2+2\Phi^2, i.e. the floor is some sort of "objective inconsistency" already seen in [3, 4, 5], and is the inverse-probability reweighting [5].

In particular, Theorem 1 of [5] states that, under Bernoulli participation with constant weights , FedAvg minimises h(x)∝∑nωnpnFn(x)h(x)\propto \sum_n\omega_np_nF_n(x), i.e. the analogous participation-weighted objective in the time-independent setting, with the same scale-free zero-bias condition ( constant). The present paper transfers this message to token algorithms.

Reduction. In the time-independent setting, the pair (st,δt)(s_t,\delta_t) is a Markov chain with stationary law π(s)Bern(ps)\pi(s)\mathrm{Bern}(p^s), and the expected update targets P,feffP,f_{\mathrm{eff}}. Combined with ∣∇f∣2≤2∣∇feff∣2+2Φ2|\nabla f|^2\le2|\nabla f_{\mathrm{eff}}|^2+2\Phi^2, which part of Theorem 1 cannot be obtained from an existing Markovian-SGD bound (e.g. using Assumption A4 in [2]) applied to this augmented chain? Please state what is technically new compared with this route.

We agree that the reviewer’s proposed reduction offers a reasonable route to a finite-time bound when availability rates and correction weights are time-independent and fefff_{\mathrm{eff}} is bounded below. Under the broader assumptions of Theorem 1, however, the reduction has two limitations that prevent it from directly yielding our convergence bound.

  • Time-independent setting: the effective objective may lack a lower bound. Our assumptions guarantee that the intended objective ff is lower bounded. To see why this matters, consider two nodes with π(1)=π(2)=12\pi(1)=\pi(2)=\frac12 and local objectives f1(x)=1−cos⁡x+xf_1(x)=1-\cos x+x and f2(x)=1−cos⁡x−xf_2(x)=1-\cos x-x. Both functions are 11-smooth, the intended objective is f(x)=1−cos⁡x≥0f(x)=1-\cos x\ge 0, and ∣fs′(x)−f′(x)∣=1\lvert f_s'(x)-f'(x)\rvert=1 for both nodes. If the first node has effective weight q≠1/2q\ne 1/2, then feff(x)=1−cos⁡x+(2q−1)xf_{\mathrm{eff}}(x)=1-\cos x+(2q-1)x is unbounded below. A descent bound in terms of feff(x0)−inf⁡xfeff(x)f_{\mathrm{eff}}(x_0)-\inf_x f_{\mathrm{eff}}(x) is therefore vacuous on this instance, while Theorem 1 gives a finite bound in terms of the initial gap of ff.
  • Time-varying setting: the effective objective may change between iterations. When the relative weights ptswtsπ(s)Pt\frac{p_t^s w_t^s\pi(s)}{P_t} change over time, the effective objective $f_{\mathrm{eff}}^{t} = \sum_s \frac{p_t^s w_t^s\pi(s) }{P_t}f_s $ can vary with tt. Even if we obtain a descent inequality for each fefftf_{\mathrm{eff}}^t, the terms on the left-hand side do not, in general, telescope when we sum over tt (e.g., E[fefft(xt+1)−fefft(xt)]≲−E[∣∇fefft(xt)∣2]\mathbb{E}[f^{t}_{\mathrm{eff}}(\mathbf{x}_{t+1}) - f_{\mathrm{eff}}^t(\mathbf{x}_t)] \lesssim -\mathbb{E}[\\|\nabla f^t_{\mathrm{eff}} (\mathbf{x}_t)\\|^2]).

The technical novelty of our work is summarized as follows:

  • Period-wise analysis of Markovian SGD. We adapt the epoch-wise analysis of permutation-based SGD (Koloskova et al., 2024) to analyze Markovian SGD. This yields an upper bound without polylogarithmic factors, algorithmic modifications, or a large-iteration condition (Theorem 1).
  • Time-varying node availability. Time-varying node availability makes the effective step size of Markovian SGD time-varying. To resolve this challenge, we introduce a new way to partition the iterations into periods (Lemma 2), which allows us to handle time-varying effective step sizes.
  • Isolating the bias term. We write each update as the product of an effective step size and a normalized gradient. The main challenge is that the normalized gradient depends on both node availability and the token trajectory. This means that isolating the bias requires accounting for both node availability and the Markovian dependence (Lemma 3).

Koloskova et al. (2024): On Convergence of Incremental Gradient for Non-Convex Smooth Functions, ICML, 2024.

Response 4: Markovian availability

The modeling assumptions are also rather simple: availability is independent over time (and i.i.d. in the setting of Corollary 1) and independent of the token's trajectory, probabilities are known and deterministic, and unavailable nodes still communicate. More interesting regimes for token algorithms (Markovian availability, availability depending on recent computation, etc.) are not covered.

Inspired by the augmented Markov chain suggested by the reviewer, we introduce the Markovian availability setting (that is, Theorem 3 in the revision):

  • Motivation. This setting is well-motivated. For example, a node may be more likely to become available when the token is nearby, and nodes with higher availability may in turn be more likely to receive the token.

  • Setting. We capture this dependence by modeling the token location and the node availability statuses jointly as a Markov chain. Specifically, we assume that the joint process ztt≥0\\{z_t\\}_{t\geq 0} (zt≔(st,δt)z_t \coloneqq (s_t,\boldsymbol{\delta_t})) of token state process st\\{s_t\\} and the availability status process δt\\{\boldsymbol{\delta_t}\\} (δt≔(δt0,δt1,…,δtS−1)\boldsymbol{\delta_t}\coloneqq(\delta_t^0,\delta_t^1,\ldots, \delta_t^{S-1})) forms a Markov chain whose stationary distribution is μ\mu.

  • Convergence rate. The convergence rate is as follows:

    =\mathcal{O} \left( \frac{ LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} }{PT} + \left(\frac{LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} \varsigma^2}{PT} \right)^{\frac{1}{2}} + \widetilde \phi^2 \right)$$ where $P \coloneqq \sum_{s} \nu(s) w_t^{s}$, $\widetilde A_1 \coloneqq \sup_{s}\frac{w^s}{P}$, $\widetilde A_3 \coloneqq \sup_{s} w^s$, and $\widetilde\tau_{\mathrm{mix}} \coloneqq \min\\{T,\tau_{\mathrm{mix}}\\}$, $F_0:=f(\mathbf{x}_0) - \inf f$, $L$ is the smoothness constant and $\varsigma$ is the heterogeneity constant, and $T$ is the total number of iterations.
  • Availability bias. The availability bias is as follows: ϕ~≔∑s∣ν(s)ws∑sν(s)ws−π(s)∣ςs\widetilde \phi \coloneqq \sum_{s} \left|\frac{\nu(s)w^s}{\sum_{s}\nu(s)w^s } - \pi(s)\right|\varsigma_s where $\nu(s) \coloneqq \Pr_\mu(s_t=s,\ \delta_t^s=1) =\sum_{\boldsymbol{\delta}\in\{0,1\}^{S}} \mu((s,\boldsymbol{\delta}))\delta^s$ denotes the stationary probability that node ss holds the token and is available.

  • Comparison with Theorem 1 (the independent availability setting). If the token location process st\\{s_t\\} and the availability statuses process δt\\{{\boldsymbol{\delta_t}}\\} satisfy the independent availability assumption (that is, Assumption 3 in the revision) with time-invariant availability pts=ps∈(0,1)p_t^s = p^s \in (0,1) for all t,st,s, the joint process {zt}\{z_t\} satisfies the Markovian availability assumption (that is, Assumption 4). Therefore, the upper bounds in Theorems 1 and 3 both apply to this special setting. Next, we compare the upper bounds derived from Theorems 1 and 3 in this special setting.

    Upper boundAvailability bias
    Theorem 1O(LF0A1(A2+A3τ^mix)PT+(LF0A1(ψ+A3τ^mixς2)PT)1/2+ϕ2)\mathcal{O}\left( \frac{ L F_0 A_1(A_2+A_3\widehat\tau_{\mathrm{mix}})}{PT}+\left(\frac{L F_0 A_1(\psi+ A_3\widehat\tau_{\mathrm{mix}}\varsigma^2)}{PT}\right)^{1/2}+\phi^2\right)ϕ=∑s∣pswsπ(s)∑spswsπ(s)−π(s)∣ςs\phi =\sum_{s}\left\vert{\frac{p^s w^s\pi(s)}{\sum_{s }p^s w^s\pi(s) }- \pi(s)}\right\vert\varsigma_s
    Theorem 3O(LF0A~1A~3τ~mixPT+(LF0A~1A~3τ~mixς2PT)12+ϕ~2)\mathcal{O} \left( \frac{ LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} }{PT} + \left(\frac{LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} \varsigma^2}{PT} \right)^{\frac{1}{2}}+\widetilde \phi^2 \right)ϕ~=∑s∣ν(s)ws∑sν(s)ws−π(s)∣ςs\widetilde \phi = \sum_{s} \left\vert\frac{\nu(s)w^s}{\sum_{s}\nu(s)w^s }-\pi(s)\right\vert\varsigma_s

    In this special setting, by the independence condition, ν(s)=psπ(s)\nu(s) = p^s \pi(s) and τ~mix=τ^mix\widetilde \tau_{\mathrm{mix}} = \widehat \tau_{\mathrm{mix}}. Then, we have the following results:

    (i) The bias terms are equal: ϕ=ϕ~\phi = \widetilde \phi.

    (ii) The error term (the second term) of Theorem 1 is less than that of Theorem 3.

    (iii) The relative magnitudes of the optimization terms (the first terms) in Theorems 1 and 3 are not necessarily determined.

    As shown above, when TT is sufficiently large, the error term dominates, and the upper bound in Theorem 1 is tighter than that in Theorem 3.

Response 5: No large-iteration requirement

No "large-iteration requirement" (Sec. 3.4): the first term LF0τmix/TLF_0\tau_{\mathrm{mix}}/T (with hidden constants of order 10710^7, as seen in the final inequality of App. A.3) is larger than LF0LF_0 unless T≳τmixT\gtrsim\tau_{\mathrm{mix}}. In [6] (v3 of the arXiv version), the burn-in is T≥2τmixln⁡τmixT\ge2\tau_{\mathrm{mix}}\ln\tau_{\mathrm{mix}}.

We would like to clarify that by "no large-iteration requirement," we mean that our bound holds for any T≥1T\geq 1, without requiring T≳τmixT\gtrsim\tau_{\mathrm{mix}}.

Convergence rateConstraint of TT
Even (2023)O((LF0+ς2)τmix′ln⁡(T)+ςπ2T+(LF0τmix′ςπ2T)12)\mathcal{O}\left(\frac{\left(LF_0 + \varsigma^2\right) \tau_{\text{mix}}'{\ln(T)} + \varsigma_{\pi}^2}{T} + \left( \frac{LF_0 \tau_{\text{mix}}' \varsigma_{\pi}^2 }{T} \right)^{\frac{1}{2}} \right)T≥2τmix′ln⁡(τmix′){\color{red}T \geq 2\tau_{\text{mix}}'\ln(\tau_{\text{mix}}')}
Our workO(LF0τ^mixT+(LF0τ^mixς2T)12)O\left(\frac{LF_0\widehat\tau_{\text{mix}}}{T} + \left( \frac{LF_0 \widehat\tau_{\text{mix}} \varsigma^2}{T} \right)^{\frac{1}{2}} \right)T≥1{\color{red}T\geq 1}

Related Notations of Even (2023) and ours are as follows: (i) τmix′≔tmix(min⁡sπ(s))\tau_{\text{mix}}' \coloneqq t_{\text{mix}}(\min_{s}\pi(s)). (ii) τ^mix=min⁡τmix,T\widehat \tau_{\mathrm{mix}} = \min\\{\tau_{\mathrm{mix}},T\\}, τmix=tmix(14)\tau_{\mathrm{mix}} = t_{\mathrm{mix}}(\frac14).

Even (2023): Stochastic Gradient Descent under Markovian Sampling Schemes, ICML, 2023.

Reviewer_BJDPOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies SGD with Markovian sampling: instead of vanilla SGD where noise and sampling are iid, here sampling follows a Markov chain. This can for instance be the case in token algorithms, in decentralized optimization. The authors add one additional difficulty, node unavailability: some nodes can be unavailable for compute. The authors characterize the bias induced by this node unavailability and how to correct for this with weights.

Critical strengths
  1. Robustness to real life constrain makes decentralized optimization and in particular token algorithms difficult to use in practice. Here, node unavailability is one of these constraints. For instance, if a node just has computed, it may for instance be unavailable for a while (no more budget?), or a node can be used in another task.
  2. The paper and the setting are well explained and very easy to follow.
Critical weaknesses
  1. The main weakness lies in the setting: node unavailability being independent of the Markov chain or of the optimization trajectory. Since the Markov chain can for instance be the communication path in the communication graph, node availability will depend heavily on their tasks. Thus, I believe that the analysis should be pushed much further, and Assumption 4 should be relaxed. Maybe a second hidden markov chain, or something like this?

  2. Related to the independent availability Bernoulli random variables of Assumption 4, it seems that a simple reweighting clearly removes the bias Φ\Phi. It is what is done in Section 3.3., and it slightly modifies the rest of the rate. However, it seems to me that for this reweighting, it simply means that the variance is increased, and the obtained rate can be explained that way. plugging in existing analyses (e.g., Even et al. 2023 ?) with this increased variance should give the same rates.

These two weaknesses seem quite important to me, and thus I am on the rejection side for this submission.

Questions for authors

Can the authors address the questions raised in the weaknesses part ?

4 comments

Response 1: Markovian availability

The main weakness lies in the setting: node unavailability being independent of the Markov chain or of the optimization trajectory. Since the Markov chain can for instance be the communication path in the communication graph, node availability will depend heavily on their tasks. Thus, I believe that the analysis should be pushed much further, and Assumption 4 should be relaxed. Maybe a second hidden Markov chain, or something like this?

As suggested, we add the Markovian availability setting in the revision (that is, Theorem 3):

  • Motivation. As pointed by the review, this setting is well-motivated. For example, a node may be more likely to become available when the token is nearby, and nodes with higher availability may in turn be more likely to receive the token.

  • Setting. We capture this dependence by modeling the token location and the node availability statuses jointly as a Markov chain. Specifically, we assume that the joint process ztt≥0\\{z_t\\}_{t\geq 0} (zt≔(st,δt)z_t \coloneqq (s_t,\boldsymbol{\delta_t})) of token state process st\\{s_t\\} and the availability status process δt\\{\boldsymbol{\delta_t}\\} (δt≔(δt0,δt1,…,δtS−1)\boldsymbol{\delta_t}\coloneqq(\delta_t^0,\delta_t^1,\ldots, \delta_t^{S-1})) forms a Markov chain whose stationary distribution is μ\mu.

  • Convergence rate. The convergence rate is as follows:

    =\mathcal{O} \left( \frac{ LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} }{PT} + \left(\frac{LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} \varsigma^2}{PT} \right)^{\frac{1}{2}} + \widetilde \phi^2 \right)$$ where $P \coloneqq \sum_{s} \nu(s) w_t^{s}$, $\widetilde A_1 \coloneqq \sup_{s}\frac{w^s}{P}$, $\widetilde A_3 \coloneqq \sup_{s} w^s$, and $\widetilde\tau_{\mathrm{mix}} \coloneqq \min\\{T,\tau_{\mathrm{mix}}\\}$, $F_0:=f(\mathbf{x}_0) - \inf f$, $L$ is the smoothness constant and $\varsigma$ is the heterogeneity constant, and $T$ is the total number of iterations.
  • Availability bias. The availability bias is as follows: ϕ~≔∑s∣ν(s)ws∑sν(s)ws−π(s)∣ςs\widetilde \phi \coloneqq \sum_{s} \left|\frac{\nu(s)w^s}{\sum_{s}\nu(s)w^s } - \pi(s)\right|\varsigma_s where $\nu(s) \coloneqq \Pr_\mu(s_t=s,\ \delta_t^s=1) =\sum_{\boldsymbol{\delta}\in\{0,1\}^{S}} \mu((s,\boldsymbol{\delta}))\delta^s$ denotes the stationary probability that node ss holds the token and is available.

  • Comparison with Theorem 1 (the independent availability setting). If the token location process st\\{s_t\\} and the availability statuses process δt\\{{\boldsymbol{\delta_t}}\\} satisfy the independent availability assumption (that is, Assumption 3 in the revision) with time-invariant availability pts=ps∈(0,1)p_t^s = p^s \in (0,1) for all t,st,s, the joint process {zt}\{z_t\} satisfies the Markovian availability assumption (that is, Assumption 4). Therefore, the upper bounds in Theorems 1 and 3 both apply to this special setting. Next, we compare the upper bounds derived from Theorems 1 and 3 in this special setting.

    Upper boundAvailability bias
    Theorem 1O(LF0A1(A2+A3τ^mix)PT+(LF0A1(ψ+A3τ^mixς2)PT)1/2+ϕ2)\mathcal{O}\left( \frac{ L F_0 A_1(A_2+A_3\widehat\tau_{\mathrm{mix}})}{PT}+\left(\frac{L F_0 A_1(\psi+ A_3\widehat\tau_{\mathrm{mix}}\varsigma^2)}{PT}\right)^{1/2}+\phi^2\right)ϕ=∑s∣pswsπ(s)∑spswsπ(s)−π(s)∣ςs\phi =\sum_{s}\left\vert{\frac{p^s w^s\pi(s)}{\sum_{s }p^s w^s\pi(s) }- \pi(s)}\right\vert\varsigma_s
    Theorem 3O(LF0A~1A~3τ~mixPT+(LF0A~1A~3τ~mixς2PT)12+ϕ~2)\mathcal{O} \left( \frac{ LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} }{PT} + \left(\frac{LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} \varsigma^2}{PT} \right)^{\frac{1}{2}}+\widetilde \phi^2 \right)ϕ~=∑s∣ν(s)ws∑sν(s)ws−π(s)∣ςs\widetilde \phi = \sum_{s} \left\vert\frac{\nu(s)w^s}{\sum_{s}\nu(s)w^s }-\pi(s)\right\vert\varsigma_s

    In this special setting, by the independence condition, ν(s)=psπ(s)\nu(s) = p^s \pi(s) and τ~mix=τ^mix\widetilde \tau_{\mathrm{mix}} = \widehat \tau_{\mathrm{mix}}. Then, we have the following results:

    (i) The bias terms are equal: ϕ=ϕ~\phi = \widetilde \phi.

    (ii) The error term (the second term) of Theorem 1 is less than that of Theorem 3.

    (iii) The relative magnitudes of the optimization terms (the first terms) in Theorems 1 and 3 are not necessarily determined.

    As shown above, when TT is sufficiently large, the error term dominates, and the upper bound in Theorem 1 is tighter than that in Theorem 3.

Response 2: Comparison with existing works

Related to the independent availability Bernoulli random variables of Assumption 4, it seems that a simple reweighting clearly removes the bias . It is what is done in Section 3.3., and it slightly modifies the rest of the rate. However, it seems to me that for this reweighting, it simply means that the variance is increased, and the obtained rate can be explained that way. plugging in existing analyses (e.g., Even et al. 2023 ?) with this increased variance should give the same rates.

We would like to clarify that substituting the large variance into a existing rate (e.g., Even (2023)) does not recover our rates. The reasons are as follows:

  • Our rate is different from the existing works. As shown in the following table, we can recover the rate of standard Markovian SGD by setting pts=1p_t^s = 1 and wts=1w_t^s = 1 in Corollary 1.

    Convergence rateConstraint of TT
    Even (2023)O((LF0+ς2)τmix′ln⁡(T)+ςπ2T+(LF0τmix′ςπ2T)12)\mathcal{O}\left(\frac{\left(LF_0 + \varsigma^2\right) \tau_{\text{mix}}'{\color{red}\ln(T)} + \varsigma_{\pi}^2}{T} + \left( \frac{LF_0 \tau_{\text{mix}}' \varsigma_{\pi}^2 }{T} \right)^{\frac{1}{2}} \right)T≥2τmix′ln⁡(τmix′){\color{red}T \geq 2\tau_{\text{mix}}'\ln(\tau_{\text{mix}}')}
    Our workO(LF0τ^mixT+(LF0τ^mixς2T)12)O\left(\frac{LF_0\widehat\tau_{\text{mix}}}{T} + \left( \frac{LF_0 \widehat\tau_{\text{mix}} \varsigma^2}{T} \right)^{\frac{1}{2}} \right)T≥1T\geq 1

    Related Notations of Even (2023) and ours are as follows: (i) τmix′≔tmix(min⁡sπ(s))\tau_{\text{mix}}' \coloneqq t_{\text{mix}}(\min_{s}\pi(s)) and ςπ2≔∑sπ(s)ςs2\varsigma_{\pi}^2 \coloneqq \sum_s \pi(s) \varsigma_s^2. (ii) τ^mix=min⁡τmix,T\widehat \tau_{\mathrm{mix}} = \min\\{\tau_{\mathrm{mix}},T\\}, τmix=tmix(14)\tau_{\mathrm{mix}} = t_{\mathrm{mix}}(\frac14) and ς=max⁡sςs\varsigma = \max_s \varsigma_s.

    Compared with Even (2023), we have the following advantages:

    (i) Free of the large-iteration condition. Our bound holds for T≥1T\geq 1, while Even (2023)'s holds for T≥2τmix′ln⁡(τmix′)T\geq 2\tau_{\text{mix}}'\ln(\tau_{\text{mix}}').

    (ii) Free of polylogarithmic factors. There are no polylogarithmic factors in our bound.

  • Our technique is different from the existing works. Unlike Even (2023), whose proof draws on the analysis of asynchronous SGD and biased SGD, our proof is based on the analysis of permutation-based SGD.

  • Our goal is different from the existing works. Our work focuses not only on developing a bias-correction algorithm but also on understanding and characterizing the bias induced by node availability.

Even (2023): Stochastic Gradient Descent under Markovian Sampling Schemes, ICML, 2023.

Dear authors,

Thanks a lot for the clarifications and the added results. I cannot check its veracity, nor do I believe adding such a result is doable for a revision, since it consists in too big a change. I still upgrade my note from 1 to 2.

Thanks for reconsidering our work. We would like to clarify that the proof for the Markovian availability setting follows the same framework as the proof for independent availability, with the main change in Lemma 5. The added result therefore builds directly on our existing analysis and requires only a limited extension of the proof, without substantial changes to the paper's main analysis.

Comments on the paper

2 comments

Global response

We thank the reviewers for the valuable comments and suggestions.

The main revisions are highlighted in blue in the revised submission.

The main changes are summarized as follows:

  • New convergence rates for the Markovian availability setting.

    Location in the paper: Theorem 3.

    Location in the responses: Responses 1 and 4.

    Time-invariant caseConvergence rateBias
    Independent settingO(LF0A1(A2+A3τ^mix)PT+(LF0A1(ψ+A3τ^mixς2)PT)1/2+ϕ2)\mathcal{O}\left( \frac{ L F_0 A_1(A_2+A_3{\widehat\tau_{\mathrm{mix}}})}{PT}+\left(\frac{L F_0 A_1({\psi}+ A_3{\widehat\tau_{\mathrm{mix}}}\varsigma^2)}{PT}\right)^{1/2} +\phi^2\right)ϕ≔∑s∣pswsπ(s)∑spswsπ(s)−π(s)∣ςs\phi \coloneqq\sum_{s} \left\vert{\frac{p^s w^s\pi(s)}{\sum_{s }p^s w^s\pi(s) } - \pi(s)}\right\vert\varsigma_s
    Markovian settingO(LF0A~1A~3τ~mixPT+(LF0A~1A~3τ~mixς2PT)12+ϕ~2)\mathcal{O} \left( \frac{ LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} }{PT} + \left(\frac{LF_0 \widetilde A_1\widetilde A_3\widetilde\tau_{\mathrm{mix}} \varsigma^2}{PT} \right)^{\frac{1}{2}} + \widetilde \phi^2 \right)ϕ~≔∑s∣ν(s)ws∑sν(s)ws−π(s)∣ςs\widetilde \phi \coloneqq \sum_{s} \left\vert\frac{\nu(s)w^s}{\sum_{s}\nu(s)w^s } - \pi(s)\right\vert\varsigma_s

    Here ν(s)≔Pr⁡μ(st=s, δts=1)\nu(s) \coloneqq \Pr_\mu(s_t=s,\ \delta_t^s=1) denotes the stationary probability that node ss holds the token and is available.

    The proof for the Markovian setting remains similar to that for the independent setting, except for Lemma 5. Thus, this improvement does not require substantial changes to the paper.

  • Improved convergence rates for the independent availability setting.

    Location in the paper: Theorem 1 and Corollary 1.

    Location in the responses: Responses 5, 8 and 12.

    Convergence rate
    OriginalO(LF0A1(A2+A3τmix)PT+(LF0A1(A2ς2+A3τmixς2)PT)1/2+ϕ2)\mathcal{O}\left( \frac{ L F_0 A_1(A_2+A_3{\color{blue}\tau_{\mathrm{mix}}})}{PT}+\left(\frac{L F_0 A_1({\color{red}A_2 \varsigma^2}+ A_3{\color{blue}\tau_{\mathrm{mix}}}\varsigma^2)}{PT}\right)^{1/2} +\phi^2\right)
    ImprovedO(LF0A1(A2+A3τ^mix)PT+(LF0A1(ψ+A3τ^mixς2)PT)1/2+ϕ2)\mathcal{O}\left( \frac{ L F_0 A_1(A_2+A_3{\color{blue}\widehat\tau_{\mathrm{mix}}})}{PT}+\left(\frac{L F_0 A_1({\color{red}\psi}+ A_3{\color{blue}\widehat\tau_{\mathrm{mix}}}\varsigma^2)}{PT}\right)^{1/2} +\phi^2\right)

    Improvements: (i) τ^mix=min⁡τmix,T≤τmix\widehat \tau_{\mathrm{mix}} = \min\\{\tau_{\mathrm{mix}},T\\} \leq \tau_{\mathrm{mix}}; (ii) ψ=∑sπ(s)ps(ws)2Pςs2≤sup⁡sps(ws)2Pς2=A2ς2\psi = \sum_{s}\pi(s)\frac{ p^s(w^s)^2 }{P} \varsigma_s^2\leq \sup_{s}\frac{p^s (w^s)^2}{P} \varsigma^2=A_2\varsigma^2.

    The improvement does not affect the experiments, as the improved bound yields similar findings.

  • Experiments on Markov chains with varying mixing behaviors (different ρ\rho values and graph topologies).

    Location in the paper: Appendices E.2 and E.3.

    Location in the responses: Responses 6 and 11.

One part of my original question remains unclear: were the corrected and uncorrected runs compared after matching their effective stepsizes? The reported averages over the latter half of training do not by themselves distinguish slower convergence from increased fluctuations or differences in update magnitude. Please clarify the stepsize settings and whether the observed trade-off persists under the matched comparison.

Thanks for the detailed response.

First, we would like to clarify our step size tuning procedure.

  • For each setting, we select the step size from a grid that minimizes the average loss over the last 50% of iterations. For example, the grid of the MNIST task is [0.00001, 0.0000215, 0.0000464, 0.0001, 0.000215, 0.000464, 0.001, 0.00215, 0.00464, 0.01, 0.0215, 0.0464]; the grid for the quadratic function task is [0.0001, 0.000215, 0.000464, 0.001, 0.00215, 0.00464, 0.01, 0.0215, 0.0464, 0.1].
  • Findings 1–3 are based on the convergence rates in Corollary 1, which is derived using the optimal step size. Since the optimal step size may differ across settings, we tune the step size separately for each setting to align with Corollary 1.

We tune the base step size γ\gamma separately for the corrected and uncorrected methods by grid search.

To further support the comparison, we also include an uncorrected baseline whose effective step size γP\gamma P matches that of the tuned corrected run.

The results are in the following table, and similar findings can be observed. Specifically, we observe: (i) From IA-1 to IA-3, the final loss increases as the availability bias increases, showing that the bias predicts the performance. (ii) For IA-1 to IA-3, correction yields substantially smaller final loss. (iii) From IA-0 to IA-3, affected by the node availability, the performance of the corrected runs deteriorates.

We hope this result answers the question "were the corrected and uncorrected runs compared after matching their effective step sizes".

[Table 1: The average error of quadratic functions with ρ=0.1\rho=0.1 over the last 50% training iterations and 10 random seeds. The new added baselines (with matching effective step size) are highlighted with "*".]

SettingFAIA-0IA-1IA-2IA-3
w/o correction0.02620.03050.59300.79820.9020
w/o correction*0.03080.60270.80830.9127
w/ correction0.03080.03860.04140.0596

[Table 2: The average training loss of logistic regression on MNIST with ρ=0.1\rho=0.1 over the last 50% training iterations and 5 random seeds. The new added baselines (with matching effective step size) are highlighted with "*".]

SettingFAIA-0IA-1IA-2IA-3
w/o correction0.30310.31990.37530.45840.6007
w/o correction*0.32020.37570.48350.6449
w/ correction0.32020.33180.35310.3975

The two-node example supports the stated stepsize restriction for the analyzed corrected method. However, this should be distinguished from a general claim that correction necessarily slows convergence. Please qualify the corresponding claims in the manuscript unless a stronger conclusion is established.

We have revised Finding 3 to state that "this implies that although correction weights can remove the availability bias, the node availability can still affect the bound." We also clarify that our findings are based on a worst-case upper bound in the iteration-invariant setting under Assumption 3. They may not hold for every instance within this setting or extend to other settings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.