SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization

Can we have your valuable feedback on our rebuttals?

Dear Reviewer ehMq, We sincerely thank you for your valuable comments and appreciate the time and effort dedicated to providing constructive feedback on our submission. We have carefully considered your suggestions and made significant efforts to address them. Given the limited timeframe of the rebuttal period, we would greatly appreciate if you could review our rebuttal and let us know if any concerns remain. Your insights are invaluable as we strive to enhance the quality of our work. Best, The authors of paper 7209

Can we have your valuable feedback on our rebuttals?

Dear Reviewer AnxT, We sincerely thank you for your valuable comments and appreciate the time and effort dedicated to providing constructive feedback on our submission. We have carefully considered your suggestions and made significant efforts to address them. Given the limited timeframe of the rebuttal period, we would greatly appreciate if you could review our rebuttal and let us know if any concerns remain. Your insights are invaluable as we strive to enhance the quality of our work. Best, The authors of paper 7209

Analysis of Consensus errors (Part 1)

**Lemma 18**: Suppose that Assumptions 1-4 hold. Then there exist constant step-sizes $\alpha, \beta, \gamma, \theta$, such that Lemma 17 holds and \begin{equation} \begin{aligned} \frac{1}{K}\sum_{k=0}^K\mathbb{E}\left[\frac{\Vert \mathbf{x}^k-\bar{\mathbf{x}}^k\Vert ^2}{n}+\frac{\Vert \mathbf{y}^k-\bar{\mathbf{y}}^k\Vert ^2}{n}\right] \lesssim_K \frac{n}{K}\left(\frac{\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert \mathbf{\Lambda}\_{za}\Vert ^2}{1-\Vert \mathbf{\Gamma}_z\Vert }+\frac{\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2\Vert \mathbf{\Lambda}\_{ya}\Vert ^2}{1-\Vert \mathbf{\Gamma}_y\Vert }\right), \end{aligned} \end{equation} where $\lesssim_K$ denotes the the asymptotic rate when $K\to \infty$. **Proof** Suppose $\alpha$, $\beta$, $\gamma$, and $\theta$ satisfy the constraints given in Eq. (89) and Eq. (90), which ensures that Theorem 1 (Lemma 17) holds. For clarity, we define the constants: \begin{equation} \begin{aligned} c_1=\frac{9\alpha^2L_{z^\star}^2}{\gamma^2\mu_g^2}+\frac{438\kappa^4\alpha^2}{\beta^2\mu_g^2}L_{y^{\star}}^2, \quad c_2=10\left(L^2+\frac{\theta\sigma_{g,2}^2}{n}\right). \end{aligned} \end{equation} Then there exist $\alpha$, $\beta$, $\gamma$, and $\theta$ that satisfy the constraints in Eq. (89) and (90), and also: \begin{equation} c_1\le 0.01 L^{-2}, \quad c_2\le 11 L^2.\cdot\cdot\cdot\cdot\cdot(*) \end{equation} It implies that $c_1 c_2<0.2$. We take such values for step-sizes in the following proof. We proceed by substituting Eq. (41) into Eq. (57), yielding: \begin{equation} \begin{aligned} \sum_{k=-1}^K\mathbb{E}[I_k] \leq 4 c_1\left(\frac{\Phi(\bar{x}^0)-\inf\Phi}{\alpha}+c_2 \sum_{k=0}^{K-1}\mathbb{E}\left[\frac{\Delta_k}{n}+I_k\right]+\frac{3\theta}{n}K\left(\sigma_{f,1}^2+2\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}\right)\right) +510\kappa^4\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right]+\frac{3\Vert z^1_{\star}\Vert ^2}{\mu_g\gamma} \\\\+\frac{6(K+1)\gamma}{\mu_g n}\left(3\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}+\sigma_{f,1}^2\right) +73\kappa^4\left(\frac{4}{\beta\mu_g}\Vert \bar{y}^{0}-y^{\star}(\bar{x}^{0})\Vert ^2 +\frac{4K\sigma_{g,1}^2}{n\mu_g}\beta\right). \end{aligned} \end{equation} Subtracting $4c_1c_2\sum_{k=0}^{K-1}\mathbb{E}[I_k]$ from both sides, we get: \begin{equation} \begin{aligned} \sum_{k=-1}^K\mathbb{E}[I_k] \lesssim \frac{\Phi(\bar{x}^0)-\inf\Phi}{\alpha}+\frac{\theta}{n}K\left(\sigma_{f,1}^2+\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}\right) +\kappa^4\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right]+\frac{\Vert z^1_{\star}\Vert ^2}{\mu_g\gamma} \\\\+\frac{K\gamma}{\mu_gn}\left(\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}+\sigma_{f,1}^2\right) +\kappa^4\left(\frac{1}{\beta\mu_g}\Vert \bar{y}^{0}-y^{\star}(\bar{x}^{0})\Vert ^2 +\frac{K\sigma_{g,1}^2}{n\mu_g}\beta\right). \end{aligned} \end{equation} Substituting Eq. (57) into Eq. (41), we obtain: \begin{equation} \begin{aligned} \frac{1}{4}\sum_{k=0}^K\mathbb{E}\left\Vert \bar{r}^{k+1}\right\Vert ^2&\\leq\frac{\Phi(\bar{x}^0)-\inf\Phi}{\alpha}+c_2\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right]+c_2c_1\sum_{k=0}^K\mathbb{E}\Vert \bar{r}^k\Vert ^2 +\\\\&c_2 \left( 510\kappa^4\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right]+\frac{3\Vert z^1_{\star}\Vert ^2}{\mu_g\gamma} +\frac{6(K+1)\gamma}{\mu_gn}\left(3\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}+\sigma_{f,1}^2\right) +73\kappa^4\left(\frac{4}{\beta\mu_g}\Vert \bar{y}^{0}-y^{\star}(\bar{x}^{0})\Vert ^2 +\frac{4K\sigma_{g,1}^2}{n\mu_g}\beta\right)\right) \\\\&+\frac{3\theta}{n}(K+1)\left(\sigma_{f,1}^2+2\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}\right). \end{aligned} \end{equation} Subtracting $c_2c_1\sum_{k=0}^K\mathbb{E}\Vert \bar{r}^k\Vert ^2$ from both sides, we get \begin{equation} \begin{aligned} \sum_{k=0}^K\mathbb{E}\left\Vert \bar{r}^{k+1}\right\Vert ^2 \lesssim&\frac{\Phi(\bar{x}^0)-\inf\Phi}{\alpha}+\kappa^4\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right]+\frac{\theta}{n}K\left(\sigma_{f,1}^2+\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}\right) \\\\&+\frac{\Vert z^1_{\star}\Vert ^2}{\mu_g\gamma} +\frac{K\gamma}{\mu_gn}\left(\sigma_{g,2}^2\frac{L_{f,0}^2}{\mu_g^2}+\sigma_{f,1}^2\right) +\kappa^4\left(\frac{1}{\beta\mu_g}\Vert \bar{y}^{0}-y^{\star}(\bar{x}^{0})\Vert ^2 +\frac{K\sigma_{g,1}^2}{n\mu_g}\beta\right). \end{aligned} \end{equation}

Analysis of Consensus errors (Part 3)

Taking $\alpha,\beta,\gamma,\theta$ satisfying Eq. 89, Eq.90, Eq.(*) and that $\kappa^4[(\eta_1+\kappa^2L_{y^{\star}}^2\eta_2)\alpha^2+\eta_3]$ is a sufficiently small constant, we can derive the following result: \begin{equation} \begin{aligned} &\frac{1}{K}\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right] \\\\ \lesssim&\frac{\kappa\eta_2\beta}{K}+\eta_2\beta^2\frac{\sigma_{g,1}^2}{n} \\\\+&\left[(\eta_1+\kappa^2L_{y^{\star}}^2\eta_2)\alpha^2+\eta_3\right]\left[\frac{1}{\alpha K}+\frac{\theta}{n}\left(\sigma_{f,1}^2+\kappa^2\sigma_{g,2}^2\right) +\frac{1}{\mu_g\gamma K} +\frac{\gamma}{\mu_gn}\left(\kappa^2\sigma_{g,2}^2+\sigma_{f,1}^2\right) +\kappa^4\left(\frac{1}{\beta\mu_g K} +\frac{\sigma_{g,1}^2}{n\mu_g}\beta\right)\right] \\\\+&\frac{\kappa^2\beta^2\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2 \Vert \mathbf{\Lambda}\_{ya}\Vert ^2}{1-\Vert \mathbf{\Gamma}_y\Vert } \sigma\_{g,1}^2+\frac{\kappa^2\alpha^2\Vert \mathbf{O}_x\Vert ^2\Vert \mathbf{O}x^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xa}\Vert ^2}{\theta K(1-\Vert \mathbf{\Gamma}_x\Vert )^2} \\\\+&\frac{\kappa^2\Vert \mathbf{O}_y\Vert ^2\mathbb{E}\Vert \hat{\mathbf{e}}_y^{0}\Vert ^2}{(1-\Vert \mathbf{\Gamma}_y\Vert )Kn}+\frac{\Vert \mathbf{O}_z\Vert ^2\mathbb{E}\Vert \hat{\mathbf{e}}_z^{0}\Vert ^2}{(1-\Vert \mathbf{\Gamma}_z\Vert )Kn} +\frac{\kappa^2\Vert \mathbf{O}_x\Vert ^2\mathbb{E}\Vert \hat{\mathbf{e}}_x^{0}\Vert ^2}{(1-\Vert \mathbf{\Gamma}_x\Vert )Kn} \\\\+&\gamma^2\frac{\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{za}\Vert ^2}{1-\Vert \mathbf{\Gamma}_z\Vert }\left(\kappa^2\sigma\_{g,2}^2+\sigma\_{f,1}^2\right) +\kappa^2\alpha^2\theta\frac{\Vert \mathbf{O}_x\Vert ^2\Vert \mathbf{O}_x^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xa}\Vert ^2}{(1-\Vert \mathbf{\Gamma}_x\Vert )^2}\left(\kappa^2\sigma\_{g,2}^2+\sigma\_{f,1}^2\right) \\\\ \lesssim&\frac{\kappa^5\eta_2\alpha}{K}+\kappa^{10}\alpha^2\frac{\sigma\_{g,1}^2}{n}+\frac{\kappa}{ K}\left[(\eta_1+\kappa^2L\_{y^{\star}}^2\eta_2)\alpha+\frac{\eta_3}{\alpha}\right] \\\\+&\left[(\eta_1+\kappa^2L\_{y^{\star}}^2\eta_2)\alpha^2+\eta_3\right]\left[\frac{\theta}{n}\left(\sigma\_{f,1}^2+\kappa^2\sigma{g,2}^2\right) +\frac{\kappa^5\alpha}{n}\left(\kappa^2\sigma\_{g,2}^2+\sigma\_{f,1}^2\right) +\kappa^9\frac{\sigma\_{g,1}^2}{n}\alpha\right] \\\\+&\frac{\kappa^2\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2 \Vert \mathbf{\Lambda}\_{ya}\Vert ^2}{1-\Vert \mathbf{\Gamma}_y\Vert } \sigma{g,1}^2\kappa^8\alpha^2+\frac{\kappa^{-1}\alpha\Vert \mathbf{O}_x\Vert ^2\Vert \mathbf{O}_x^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xa}\Vert ^2}{ K(1-\Vert \mathbf{\Gamma}_x\Vert )^2} \\\\+&\alpha^2\frac{\kappa^{10}\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{ya}\Vert ^2\Vert {\mathbf{\Lambda}}\_{yb}^{-1}\Vert ^2\zeta^y_0}{K(1-\Vert \mathbf{\Gamma}_y\Vert )}+\alpha^2\frac{\kappa^{8}\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{za}\Vert ^2\Vert {\mathbf{\Lambda}}\_{zb}^{-1}\Vert ^2\zeta^z_0}{K(1-\Vert \mathbf{\Gamma}_z\Vert )} \\\\+&\alpha^2\frac{\kappa^2\Vert \mathbf{O}_x\Vert ^2\Vert \mathbf{O}_x^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xa}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xb}^{-1}\Vert ^2\zeta^x_0}{K(1-\Vert \mathbf{\Gamma}_x\Vert )} \\\\+&\kappa^8\alpha^2\frac{\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{za}\Vert ^2}{1-\Vert \mathbf{\Gamma}_z\Vert }\left(\kappa^2\sigma\_{g,2}^2+\sigma\_{f,1}^2\right) +\kappa^2\alpha^2\theta\frac{\Vert \mathbf{O}_x\Vert ^2\Vert \mathbf{O}_x^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{xa}\Vert ^2}{(1-\Vert \mathbf{\Gamma}_x\Vert )^2}\left(\kappa^2\sigma\_{g,2}^2+\sigma\_{f,1}^2\right), \end{aligned} \end{equation} where the second inequality uses Eq.90. From Eq. 89 and Eq. 90, we can determine the following asymptotic orders for $\alpha,\beta,\gamma$ and $\theta$ \begin{equation} \alpha=\mathcal{O}\left(\kappa^{-4}\sqrt{\frac{n}{K\sigma^2}}\right),\quad \beta=\mathcal{O}\left(\sqrt{\frac{n}{K\sigma^2}}\right),\quad \gamma=\mathcal{O}\left(\sqrt{\frac{n}{K\sigma^2}}\right),\quad \theta=\mathcal{O}\left(\kappa\sqrt{\frac{n}{K\sigma^2}}\right). \end{equation} Then we get \begin{equation} \begin{aligned} &\frac{1}{K}\sum_{k=0}^K\mathbb{E}\left[\frac{\Delta_k}{n}\right] \lesssim_K \frac{\kappa^2n}{K}\left(\frac{\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{za}\Vert ^2}{1-\Vert \mathbf{\Gamma}_z\Vert }+\frac{\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{ya}\Vert ^2}{1-\Vert \mathbf{\Gamma}_y\Vert }\right), \end{aligned} \end{equation} where $\lesssim_K$ denotes the the asymptotic rate when $K\to \infty$.

Analysis of Consensus errors (Part 4)

Then using Eq. 36 and the definition of $\Delta_k$ , we get \begin{equation} \begin{aligned} &\frac{1}{K}\sum\_{k=0}^K\mathbb{E}\left[\frac{\Vert \mathbf{x}^k-\bar{\mathbf{x}}^k\Vert ^2}{n}+\frac{\Vert \mathbf{y}^k-\bar{\mathbf{y}}^k\Vert ^2}{n}\right] \lesssim_K \frac{n}{K}\left(\frac{\Vert \mathbf{O}_z\Vert ^2\Vert \mathbf{O}_z^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{za}\Vert ^2}{1-\Vert \mathbf{\Gamma}_z\Vert }+\frac{\Vert \mathbf{O}_y\Vert ^2\Vert \mathbf{O}_y^{-1}\Vert ^2\Vert {\mathbf{\Lambda}}\_{ya}\Vert ^2}{1-\Vert \mathbf{\Gamma}_y\Vert }\right). \end{aligned} \end{equation} In particular, the corresponding result of SPARKLE variants that using EXTRA, ED or GT is \begin{equation} \begin{aligned} &\frac{1}{K}\sum\_{k=0}^K\mathbb{E}\left[\frac{\Vert \mathbf{x}^k-\bar{\mathbf{x}}^k\Vert ^2}{n}+\frac{\Vert \mathbf{y}^k-\bar{\mathbf{y}}^k\Vert ^2}{n}\right] \lesssim_K \frac{n}{K}\left(\frac{1}{1-\rho_y}+\frac{1}{1-\rho_z}\right), \end{aligned} \end{equation} where $1-\rho_y,1-\rho_z$ are spectrum gaps of relevant mixing matrices for $y,z$ respectively. We finish the proof. **To our knowledge, it is the first theoretical result of consensus errors for decentralized stochastic bilevel algorithms under the condition that the asymptotic convergence rate shows linear speedup.**

Can we have your valuable feedback on our rebuttals?

Dear Reviewer 4NJf, We sincerely thank you for your valuable comments and appreciate the time and effort dedicated to providing constructive feedback on our submission. We have carefully considered your suggestions and made significant efforts to address them. Given the limited timeframe of the rebuttal period, we would greatly appreciate if you could review our rebuttal and let us know if any concerns remain. Your insights are invaluable as we strive to enhance the quality of our work. Best, The authors of paper 7209

Supplement to the omitted parts of the rebuttal to Reviewer E8rC

- [**Improved rates**] All SPARKLE variants achieve state-of-the-art convergence rates compared to existing algorithms. In particular, it is theoretically established that SPARKLE has shorter transient stages and demonstrates better robustness to network topologies. These refined results surpass those achievable through existing analyses. **(1)** A fundamental challenge is capturing the common essence of these heterogeneity correction algorithms. A key step in our proof involves the transformation that utilizes the unified primal-dual forms outlined in Section C.1.2 (Appendix) and the reformulation of the update rules for SPARKLE, as specified in Equations (33-35). We address the biases of each variable $s \in \{x, y, z\}$ along with their corresponding gradients in aggregated vectors $\hat{\mathbf{e}}_s$. By analyzing the coupled consensus errors simultaneously and recursively through the contractive matrices $\Gamma_s$, we obtain tighter bounds than those found in related works. **(2)** Though our bilevel algorithms can formally reduce to single-level algorithms under certain trivial lower-level loss functions (see Section **C.4**, Appendix), deriving the convergence rates for single-level algorithms directly from the bilevel framework analysis presents its own challenges. We rigorously analyze the hyper-gradient norms in Lemma 8 and provide a tight upper bound. The precise results in Lemma 8 are crucial for deriving the convergence rates of the single-level degeneration versions of the bilevel algorithms within our framework. - [**More relaxed assumptions**] Our theoretical analysis achieves state-of-the-art convergence rates under more relaxed assumptions compared to existing algorithms. **(1) Lipschitz Continuous Loss Functions.** Most analyses in existing works rely on Lipschitz continuity of the upper-level loss functions $f_i$ and lower-level loss functions $g_i$ [2-6]. In contrast, we handle the bias of gradient estimation through additional steps, which only require high-order Lipschitz constants. For instance, we estimate the bias of $\nabla_1 f_i(x_i^k, y_i^{k+1})$ as follows: $$\|\nabla_1 f_i(x_i^k, y_i^{k+1}) - \nabla_1 f_i(\bar{x}^k, y^{\star}(\bar{x}^k))\|^2 \leq 2 \|\nabla_1 f_i(x_i^k, y_i^{k+1}) - \nabla_1 f_i(\bar{x}^k, \bar{y}^{k+1})\|^2 + 2 \|\nabla_1 f_i(\bar{x}^k, \bar{y}^{k+1}) - \nabla_1 f_i(\bar{x}^k, y^{\star}(\bar{x}^k))\|^2 \leq 2L_{f,1}^2 (\|x_i^k - \bar{x}^k\|^2 + \|y_i^{k+1} - \bar{y}^{k+1}\|^2 + \|\bar{y}^{k+1} - y^{\star}(\bar{x}^k)\|^2).$$In contrast, other works may bound gradient or gradient estimation errors directly by a constant, based on assumptions of Lipschitz continuous loss functions. **(2) Bounded Gradient Dissimilarity.** We utilize heterogeneity correction techniques such as EXTRA, ED, and GT to remove the assumptions on bounded gradient dissimilarity. A common feature of these techniques is that each eigenvalue of the corresponding $L_s$ matrices in **Assumption 3** has magnitude less than 1, ensuring that $\|\Gamma_s\|<1$ in basic transformations (**Eq. (33-35), Appendix**). This allows us to recursively bound consensus errors using $\Gamma_s$. In contrast, other decentralized algorithms, such as Decentralized SGD, do not satisfy Assumption 3 and therefore rely on additional assumptions.