Proof. We use induction to show Eq. ?? .

Base Case: for \(k = 1\), by Eq. ?? and the definition of \(M\), \(d^{(2)}\leq a+b + e^{(1)} \leq a + b + M\), which also satisfies Eq. ?? .

Induction Hypothesis: suppose Eq. ?? holds for 1 to \(k-1\) (where \(2 \leq k \leq K\)), i.e., \[\begin{align} d^{(l)} \leq \Big(\frac{a}{l-1} + b(1+\log (l-1)) + M \Big)\sum_{i=0}^{l-2} (2c(1+\log (l-1)))^{i} \end{align}\] which implies \[\begin{align} d^{(l)} \leq \Big(\frac{a}{l-1} + b(1+\log k) + M \Big)\sum_{i=0}^{l-2} (2c(1+\log k))^{i} \end{align}\]

Now for \(d^{(k+1)}\), by Eq. ?? , \[\begin{align} d^{(k+1)} &\leq \frac{a}{k} + b(1+\log k) + c\sum_{l=2}^{k} \frac{d^{(l)}}{k-l+2} + \sum_{l=1}^{k} \frac{e^{(l)}}{k-l+1}\\ &\leq \frac{a}{k} + b(1+\log k) + c\sum_{l=2}^{k} \frac{d^{(l)}}{k-l+2} + M\\ \label{eq:breg95div95rel95interm1} &\leq \frac{a}{k} + ac \sum_{l=2}^{k} \sum_{i=0}^{i-2} \frac{(2c(1+\log k))^i}{(k-l+2) (l-1)} \\ \nonumber &\quad + \Big( b(1+\log k) + M \Big) \Big(1 + c \sum_{l=2}^{k} \sum_{i=0}^{l-2} \frac{(2c(1+\log k))^i}{k-l+2} \Big) \end{align}\tag{7}\]

Note that \[\begin{align} c \sum_{l=2}^{k} \sum_{i=0}^{i-2} \frac{(2c(1+\log k))^i}{(k-l+2) (l-1)} &= c \sum_{i=0}^{k-2} (2c(1+\log k))^i \Big(\sum_{l=2+i}^{k} \frac{1}{(k-l+2)(l-1)} \Big)\\ &= \frac{c}{k+1}\sum_{i=0}^{k-2} (2c(1+\log k))^{i} \Big( \sum_{l=2+i}^{k} \frac{1}{k-l+2} + \frac{1}{l-1} \Big)\\ &\leq \frac{c}{k+1}\sum_{i=0}^{k-2} (2c(1+\log k))^{i} \sum_{l=1}^{k} \frac{2}{l}\\ &\leq \frac{\sum_{i=0}^{k-2} (2c(1+\log k))^{i+1}}{k+1}\\ &\leq \frac{\sum_{i=0}^{k-1} (2c(1+\log k))^i}{k+1}\\ \label{eq:breg95div95rel95interm2} &\leq \frac{\sum_{i=1}^{k-1} (2c (1+\log k))^i}{k} \end{align}\tag{8}\] and \[\begin{align} c \sum_{l=2}^{k}\sum_{i=0}^{l-2} \frac{(2c(1+\log k))^i}{k-l+2} &= c \sum_{i=0}^{k-2} (2c(1+\log k))^i \sum_{l=2+i}^{k} \frac{1}{k-l+2} \leq c \sum_{i=0}^{k-2} (2c(1+\log k))^i \sum_{l=1}^{k} \frac{1}{l}\\ &\leq c(1+\log k)\sum_{i=0}^{k-2} (2c(1+\log k))^{i} \leq \sum_{i=0}^{k-2} (2c(1+\log k))^{i+1}\\ \label{eq:breg95div95rel95interm3} &\leq \sum_{i=1}^{k-1} (2c(1+\log k))^{i} \end{align}\tag{9}\]

Combining Eq. 7 , Eq. 8 and Eq. 9 , \[\begin{align} d^{(k+1)} &\leq \frac{a}{k} + \frac{a}{k} \sum_{i=1}^{k-1}(2c(1+\log k))^{i} + \Big(b (1+\log k) + M \Big)\Big( 1 + \sum_{i=1}^{k-1}(2c(1+\log k))^{i} \Big)\\ &= \Big( \frac{a}{k} + b(1+\log k) + M \Big) \sum_{i=0}^{k-1} (2c(1+\log k))^{i} \end{align}\] which finishes the induction. ◻

Proof of Lemma 9. It suffices to only consider \({\mathbf{x}}\in \text{dom}(\psi)\).

Let \({\mathbf{g}}^{(k)} = \sum_{i=1}^{n_d^{(k)}}\Big( \nabla f_{\pi_i^{(k)}} ({\mathbf{x}}_i^{(k)}) + \rho_i^{(k)}\Big) + \sum_{i=n_d^{(k)}+1}^{n} \Big( \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_{i}^{(k)}) + \rho_i^{(k)}\Big)\).

According to the update rule in 1, \({\mathbf{x}}_{n+1}^{(k)} = {\mathbf{x}}_1^{(k)} - \eta \cdot {\mathbf{g}}^{(k)}\). Observe that \[\begin{align} {\mathbf{x}}_1^{(k+1)} &= \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in \mathbb{R}^d} \Big\{ n \psi({\mathbf{x}}) + \frac{\| {\mathbf{x}}- {\mathbf{x}}_{n+1}^{(k)}\|^2}{2\eta} \Big\} = \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in \mathbb{R}^d} \Big\{ n\psi({\mathbf{x}}) + \frac{\| {\mathbf{x}}- {\mathbf{x}}_1^{(k)} + \eta \cdot {\mathbf{g}}^{(k)}\|^2}{2 \eta} \Big\}\\ &= \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in\mathbb{R}^d}\Big\{ n \psi({\mathbf{x}}) + \frac{\|{\mathbf{x}}- {\mathbf{x}}_1^{(k)}\|^2 + \eta^2 \|{\mathbf{g}}^{(k)}\|^2 + 2 \langle {\mathbf{x}}- {\mathbf{x}}_1^{(k)}, \eta {\mathbf{g}}^{(k)} \rangle}{2 \eta} \Big\}\\ &= \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in \mathbb{R}^d}\Big\{ n \psi({\mathbf{x}}) + \frac{\|{\mathbf{x}}- {\mathbf{x}}_1^{(k)}\|^2}{2\eta} + \langle {\mathbf{x}}- {\mathbf{x}}_1^{(k)}, {\mathbf{g}}^{(k)}\rangle \Big\} \end{align}\]

By the first-order optimality condition, there exists some vector \(\nabla \psi({\mathbf{x}}_1^{(k+1)})\) in the subgradient of \(\psi({\mathbf{x}}_1^{(k+1)})\) such that \[\begin{align} n \nabla \psi ({\mathbf{x}}_1^{(k+1)}) + {\mathbf{g}}^{(k)} + \frac{{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}}{\eta} = \mathbf{0} \iff {\mathbf{g}}^{(k)} = -n \nabla \psi({\mathbf{x}}_1^{(k+1)}) + \frac{{\mathbf{x}}_1^{(k)} - {\mathbf{x}}_1^{(k+1)}}{\eta} \end{align}\]

Therefore, for \({\mathbf{z}}\in \text{dom}(\psi)\), \[\begin{align} \nonumber &\langle {\mathbf{g}}^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &= n \langle \nabla \psi({\mathbf{x}}_1^{(k+1)}), {\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\rangle + \frac{1}{\eta}\langle {\mathbf{x}}_1^{(k)} - {\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &\stackrel{\text{(a)}}{\leq} n\Big( \psi({\mathbf{z}}) - \psi({\mathbf{x}}_1^{(k+1)}) - \frac{\mu_\psi}{2}\|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2\Big) + \frac{1}{\eta}\langle {\mathbf{x}}_1^{(k)} - {\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &= n\Big( \psi({\mathbf{z}}) - \psi({\mathbf{x}}_1^{(k+1)}) - \frac{\mu_\psi}{2}\|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2\Big) + \frac{1}{2\eta}\Big(\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2 - \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 - \|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \Big)\\ \label{eq:dot95form951} &= n\Big( \psi({\mathbf{z}}) - \psi({\mathbf{x}}_1^{(k+1)})\Big) + \frac{\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2}{2\eta} - (\frac{1}{2\eta} + \frac{n\mu_\psi}{2}) \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 - \frac{1}{2\eta}\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \end{align}\tag{10}\] where (a) is by Assumption 4 on the \(\mu_\psi\)-strong convexity of \(\psi\).

By the definition of \({\mathbf{g}}^{(k)}\), \[\begin{align} \nonumber &\langle {\mathbf{g}}^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle = \langle \sum_{i=1}^{n_d^{(k)}}\Big( \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) + \rho_i^{(k)}\Big) + \sum_{i=n_d^{(k)}+1}^{n} \Big( \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) + \rho_i^{(k)} \Big) , {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \label{eq:dot95interm} &= \sum_{i=1}^{n_d^{(k)}} \langle \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle + \sum_{i=n_d^{(k)}+1}^{n} \langle \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}} \rangle + \sum_{i=1}^{n}\langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \end{align}\tag{11}\]

Since for \(i \leq n_d^{(k)}\), \[\begin{align} &B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) = f_{\pi_i^{(k)}}({\mathbf{x}}_1^{(k+1)}) - f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \langle \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_i^{(k)}\rangle\\ &B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) = f_{\pi_i^{(k)}}({\mathbf{z}}) - f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \langle \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}), {\mathbf{z}}- {\mathbf{x}}_i^{(k)}\rangle \end{align}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} &B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) = f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_1^{(k+1)}) - f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \langle \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_i^{(k)}\rangle\\ &B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) = f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \langle \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}), {\mathbf{z}}- {\mathbf{x}}_i^{(k)} \rangle \end{align}\] there is for \(i \leq n_d^{(k)}\), \[\begin{align} \label{eq:dot95to95bregmandiv95priv} &\sum_{i=1}^{n_d^{(k)}}\langle \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \\ \nonumber &= \sum_{i=1}^{n_d^{(k)}}\Big(f_{\pi_i^{(k)}}({\mathbf{x}}_1^{(k+1)}) - f_{\pi_i^{(k)}}({\mathbf{z}}) - B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) + B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \end{align}\tag{12}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} \label{eq:dot95to95bregmandiv95pub} &\sum_{i=n_d^{(k)}+1}^{n}\langle \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &= \sum_{i=n_d^{(k)}+1}^{n}\Big( f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_1^{(k+1)}) - f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) + B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \end{align}\tag{13}\] Therefore, summing up Eq. 12 and Eq. 13 , we have \[\begin{align} \nonumber &\sum_{i=1}^{n_d^{(k)}} \langle \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle + \sum_{i=n_d^{(k)}+1}^{n} \langle \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}), {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &= \sum_{i=1}^{n_d^{(k)}}\Big(f_{\pi_i^{(k)}}({\mathbf{x}}_1^{(k+1)}) - f_{\pi_i^{(k)}}({\mathbf{z}})\Big) + \sum_{i=n_d^{(k)}+1}^{n}\Big( f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_1^{(k+1)}) - f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \Big)\\ \nonumber &\quad - \sum_{i=1}^{n_d^{(k)}}\Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) - \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big)\\ \label{eq:dot95to95bregmandiv} &= n F^{(k)}({\mathbf{x}}_1^{(k+1)}) - n F^{(k)}({\mathbf{z}}) - \sum_{i=1}^{n_d^{(k)}}\Big( B_{f_{\pi_i^{(k)}}^{(k, priv)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}^{(k, priv)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big)\\ \nonumber &\quad - \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \end{align}\tag{14}\]

Hence, plugging Eq. 14 back to Eq. 11 , there is \[\begin{align} \label{eq:dot95form952} &\langle {\mathbf{g}}^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle = n F^{(k)}({\mathbf{x}}_1^{(k+1)}) - n F^{(k)}({\mathbf{z}}) + \sum_{i=1}^{n}\langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &\quad - \sum_{i=1}^{n_d^{(k)}}\Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) - \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \end{align}\tag{15}\]

Recall that \(G({\mathbf{x}}) = F({\mathbf{x}}; {\mathsf{D}}) + \psi({\mathbf{x}})\) is the target objective (see Eq. 5 ) and \(G^{(k)}({\mathbf{x}}) = F^{(k)}({\mathbf{x}}; {\mathsf{D}}^{(k)} \cup {\mathsf{P}}^{(k)}) + \psi({\mathbf{x}})\) (see Eq. 6 ) is the objective used in the \(k\)-th epoch during optimization for \(k\in [K]\).

Now, by Eq. 10 and Eq. 15 , after rearranging \[\begin{align} &G^{(k)}({\mathbf{x}}_1^{(k+1)}) - G^{(k)}({\mathbf{z}}) \leq \frac{\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2}{2n \eta} - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 - \frac{1}{2n \eta}\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\\ \nonumber &\quad + \frac{1}{n} \sum_{i=1}^{n_d^{(k)}}\Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big)\\ \nonumber &\quad + \frac{1}{n} \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) + \frac{1}{n}\sum_{i=1}^{n}\langle -\rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \end{align}\]

And following the above, for any \({\mathbf{z}}\in \mathbb{R}^d\) and \(s\in [K]\), \[\begin{align} &G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}}) =\left( G^{(k)}({\mathbf{x}}_1^{(k+1)}) - G^{(k)}({\mathbf{z}}) \right) + \left( G({\mathbf{x}}_1^{(k+1)}) - G^{(k)}({\mathbf{x}}_1^{(k+1)}) \right) - \left( G({\mathbf{z}}) - G^{(k)}({\mathbf{z}}) \right)\\ &\leq H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}}) + \frac{\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2}{2n \eta} - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 - \frac{1}{2n \eta}\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\\ \nonumber &\quad + \frac{1}{n} \sum_{i=1}^{n_d^{(k)}}\Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big)\\ \nonumber &\quad + \frac{1}{n} \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) + \frac{1}{n}\sum_{i=1}^{n}\langle -\rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \end{align}\] ◻

Proof of Lemma 10. By Lemma 6, for \(i \leq n_d^{(k)}\), and permutation \(\pi_i^{(k)} \in \Pi_n\), \[\begin{align} &B_{f_{\pi_i^{(k)}}} ({\mathbf{x}}_{1}^{(k+1)}, {\mathbf{x}}_i^{(k)}) \leq \frac{ L_{\pi_i^{(k)}}}{2} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_{i}^{(k)}\|^2 \leq L_{\pi_i^{(k)}} \Big( \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 + \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)} \|^2 \Big)\\ &B_{f_{\pi_i^{(k)}}} ({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \geq \frac{\left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2}{2 L_{\pi_i^{(k)}}} \end{align}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} &B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) \leq \frac{\widetilde{L}_{i-n_d^{(k)}}^{(k)}}{2} \|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_i^{(k)}\|^2 \leq \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big( \|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 + \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 \Big)\\ &B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \geq \frac{\left\| \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \right\|^2}{2\widetilde{L}_{i-n_d^{(k)}}^{(k)}} \end{align}\] Therefore, \[\begin{align} \nonumber &\frac{1}{n} \Big(\sum_{i=1}^{n_d^{(k)}} \Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_{1}^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) + \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k,pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \Big) \\ \nonumber &\leq \frac{1}{n}\sum_{i=1}^{n_d^{(k)}} \Big( L_{\pi_i^{(k)}} \Big(\|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 + \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 \Big) - \frac{ \left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2}{2 L_{\pi_i^{(k)}}} \Big)\\ \nonumber &\quad + \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n}\Big( \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big( \|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)} \|^2 + \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\Big) - \frac{\left\| \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \right\|^2}{2\widetilde{L}_{i-n_d^{(k)}}^{(k)}} \Big)\\ \label{eq:breg95diff95interm952} &= \widehat{L}^{(k)} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 + \frac{1}{n} \Big( \underbrace{\sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2}_{:= I_1} + \underbrace{\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2}_{:= I_2} \Big)\\ \nonumber &\quad - \frac{1}{n} \Big( \sum_{i=1}^{n_d^{(k)}} \frac{ \left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2}{2 L_{\pi_{i}^{(k)}}} + \sum_{i=n_d^{(k)}+1}^{n} \frac{\left\| \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \right\|^2}{2\widetilde{L}_{i-n_d^{(k)}}^{(k)}} \Big) \end{align}\tag{16}\] where recall that \(\widehat{L}^{(k)} = \frac{1}{n}\sum_{i=1}^{n} \left( \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} + \sum_{j=1}^{n-n_d^{(k)}} \widetilde{L}_j^{(k)} \right)\). Now we bound terms \(I_1 \triangleq \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\) (in Part I) and \(I_2 \triangleq \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\) (in Part II) as follows:

Part I: For \(i \leq n_d^{(k)}\), \[\begin{align} I_1 &\triangleq \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 = \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 = \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \eta^2 \Big\| \sum_{j=1}^{i-1} (\nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}) \Big\|^2 }\\ \nonumber &= \eta^2 \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \Big(\nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) + \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) + \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) + \rho_j^{(k)} \Big)\Big\|^2\\ \label{eq:breg95diff95interm951} &\leq \eta^2 \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}}\Big( 4\Big\| \sum_{j=1}^{i-1} \Big(\nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big) \Big\|^2 \\ \nonumber &\quad + 4 \Big\|\sum_{j=1}^{i-1} \Big( \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big) \Big\|^2 + 4\Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2 + 4\Big\| \sum_{j=1}^{i-1}\rho_j^{(k)} \Big\|^2 \Big) \end{align}\tag{17}\] We proceed by bounding the first two terms in Eq. 17 separately. First, \[\begin{align} \nonumber &\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}}\Big\|\sum_{j=1}^{i-1} \Big( \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big)\Big\|^2\\ \nonumber &\leq \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} (i-1)\sum_{j=1}^{i-1} \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2\\ \nonumber &= \sum_{j=1}^{n_d^{(k)}-1} \Big( \sum_{i=j+1}^{n_d^{(k)}} L_{\pi_i^{(k)}} (i-1) \Big)\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 \Big) \\ \nonumber &\leq \sum_{j=1}^{n_d^{(k)}-1} n (\sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}}) \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 \\ & \label{eq:breg95diff95term951} \leq n (\sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}}) \sum_{j=1}^{n_d^{(k)}} \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 \end{align}\tag{18}\]

Next, \[\begin{align} \nonumber &\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \left\| \sum_{j=1}^{i-1} \Big( \nabla f_{\pi_{j}^{(k)}}({\mathbf{z}}) - \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big) \right\|^2\\ \nonumber &\stackrel{\text{(a)}}{\leq} \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} 2 \Big(\sum_{j=1}^{i-1} L_{\pi_j^{(k)}} \Big) \Big( \sum_{l=1}^{i-1} B_{f_{\pi_l^{(k)}}}({\mathbf{z}}, {\mathbf{x}}^*) \Big) \leq 2 n L \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big(\sum_{l=1}^{i-1} B_{f_{\pi_l^{(k)}}}({\mathbf{z}}, {\mathbf{x}}^*) \Big)\\ &\stackrel{\text{(b)}}{\leq} 2 n L \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big(\sum_{l=1}^{n} B_{f_{\pi_l}^{(k)}}({\mathbf{z}}, {\mathbf{x}}^*) \Big) \label{eq:breg95diff95term952} = 2 n^2 L B_F({\mathbf{z}}, {\mathbf{x}}^*) \cdot \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \end{align}\tag{19}\] where \((a)\) is by Lemma 6 and \((b)\) is due to \(B_{f_i^{(k)}}({\mathbf{z}}, {\mathbf{x}}^*) \geq 0, \forall {\mathbf{z}}\in\mathbb{R}^{d}, i\in [n]\).

Plugging Eq. 18 and Eq. 19 back to Eq. 17 , there is

\[\begin{align} \label{eq:breg95div95interm95ub} I_1 \triangleq & \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 \\ \nonumber &\leq 4 \eta^2 n (\sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}}) \sum_{j=1}^{n_d^{(k)}} \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 \\ \nonumber &\quad + 8 \eta^2 n^2 L B_F({\mathbf{z}}, {\mathbf{x}}^*) \cdot \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} + 4 \eta^2 \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}} ({\mathbf{x}}^*) \Big\|^2 + 4 \eta^2 \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1}\rho_j^{(k)}\Big\|^2 \end{align}\tag{20}\]

Part II: Similarly, for \(n_d^{(k)} < i \leq n\), \[\begin{align} \nonumber I_2 \triangleq &\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\\ &= \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \eta^2 \Big\| \sum_{j=1}^{n_d^{(k)}}(\nabla f_{\pi_{j}^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}) + \sum_{j=n_d^{(k)}+1}^{i-1} (\nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}) \Big\|^2 }\\ \nonumber &=\eta^2 \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\| \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) + \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}} ({\mathbf{z}}) - \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*}) + \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*})\\ \nonumber &\quad + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\\ \nonumber &\quad + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*}) + \sum_{j=n_d^{(k)}+1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*}) + \sum_{j=1}^{i-1} \rho_j^{(k)} \Big\|^2 \\ \nonumber &= \eta^2 \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\|\Big( \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)})\\ \nonumber &\quad - \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{n} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \Big) + \Big( \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big) \\ \nonumber &\quad + \Big( \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*}) \Big) + \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^{*}) + \sum_{j=1}^{i-1} \rho_j^{(k)} \Big\|^2\\ \label{eq:breg95diff95interm95195pub} &\leq \eta^2 \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big( 5 \Big\| \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) \\ \nonumber &\quad - \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \Big\|^2 + 5\Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2\\ \nonumber &\quad + 5\Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2 + 5\Big\|\sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2 + 5\Big\|\sum_{j=1}^{i-1}\rho_j^{(k)} \Big\|^2 \Big) \end{align}\tag{21}\]

We proceed by bounding the first three terms in Eq. 21 separately. First, \[\begin{align} \nonumber &\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\| \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \Big\|^2\\ \nonumber &\leq \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} (i-1) \Big(\sum_{j=1}^{n_d^{(k)}} \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 + \sum_{j=n_d^{(k)}+1}^{i-1}\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}})\Big\|^2 \Big)\\\ \nonumber &\leq \sum_{j=1}^{n_d^{(k)}} \Big(\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}(i-1)\Big)\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2\\ \nonumber &\quad + \sum_{j=n_d^{(k)}+1}^{n-1} \Big(\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}(i-1)\Big)\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}})\Big\|^2\\ \label{eq:breg95diff95term95195pub} &\leq \sum_{j=1}^{n_d^{(k)}} n \Big(\sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big) \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 \\ \nonumber &\quad + \sum_{j=n_d^{(k)}+1}^{n} n \Big(\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big) \Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}})\Big\|^2 \end{align}\tag{22}\] Next, \[\begin{align} \label{eq:breg95diff95term95dissim95pub} &\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2\\ \nonumber &\leq L^{(k)*} \sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \end{align}\tag{23}\] Moreover, \[\begin{align} \nonumber &\sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2\\ \nonumber &\stackrel{\text{(a)}}{\leq} \sum_{i= n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \cdot 2\Big( \sum_{j=1}^{i-1} L_{\pi_j^{(k)}} \Big) \Big( \sum_{j=1}^{i-1} B_{\pi_j^{(k)}}({\mathbf{z}}, {\mathbf{x}}^*) \Big)\\ \nonumber &\stackrel{\text{(b)}}{\leq} \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \cdot 2\Big( \sum_{j=1}^{i-1} L_{\pi_j^{(k)}} \Big) \Big( \sum_{j=1}^{n} B_{\pi_j^{(k)}}({\mathbf{z}}, {\mathbf{x}}^*) \Big)\\ &\leq 2 \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \cdot n L \cdot \Big( \sum_{j=1}^{n} B_{j}({\mathbf{z}}, {\mathbf{x}}^*) \Big) \label{eq:breg95diff95term95295pub} \leq 2 n^2 L B_F({\mathbf{z}}, {\mathbf{x}}^*) \cdot \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \end{align}\tag{24}\] where \((a)\) is by Lemma 6 and \((b)\) is due to \(B_{f_i}({\mathbf{z}}, {\mathbf{x}}^*) \geq 0, \forall {\mathbf{z}}\in\mathbb{R}^{d}, i\in [n]\). Plugging Eq. 22 , Eq. 23 and Eq. 24 back to Eq. 21 , there is \[\begin{align} \label{eq:breg95div95interm95ub95pub} &I_2 = \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\\ \nonumber &\leq 5 \eta^2 n (\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}) \sum_{j=1}^{n_d^{(k)}} \Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2\\ \nonumber &\quad + 5\eta^2 n (\sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}) \sum_{j=n_d^{(k)}+1}^{n}\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}})\Big\|^2\\ \nonumber &\quad + 5\eta^2 L^{(k)*} \sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 + 10 \eta^2 n^2 L B_F({\mathbf{z}}, {\mathbf{x}}^*) \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\\ \nonumber &\quad + 5\eta^2 \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + 5\eta^2 \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 \end{align}\tag{25}\]

Combining Eq. 20 and Eq. 25 , there is \[\begin{align} \label{eq:breg95div95interm95ub95sum} &\frac{1}{n} (I_1 + I_2) = \frac{1}{n}\Big( \sum_{i=1}^{n_d^{(k)}} L_{\pi_i^{(k)}} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)} \|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \|{\mathbf{x}}_i^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\Big) \\ \nonumber &\leq 5\eta^2 n \widehat{L}^{(k)} \sum_{j=1}^{n_d^{(k)}}\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_{j}^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 + 5\eta^2 n \widehat{L}^{(k)} \sum_{j=n_d^{(k)}+1}^{n}\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}( {\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}})\Big\|^2 \\ \nonumber &\quad + 10 \eta^2 n^2 \widehat{L}^{(k)} L B_F({\mathbf{z}}, {\mathbf{x}}^*) + 5 \eta^2 \frac{1}{n} \Big(\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 \Big)\\ \nonumber &\quad + 5\eta^2 \frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2\Big)\\ \nonumber &\quad + 5\eta^2 L^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \end{align}\tag{26}\]

Hence, plugging Eq. 26 back to Eq. 16 , there is \[\begin{align} &\frac{1}{n} \Big(\sum_{i=1}^{n_d^{(k)}} \Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_{1}^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) + \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k,pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \Big) \\ &= \widehat{L}^{(k)} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \\ \nonumber &\quad + 5\eta^2 n \widehat{L}^{(k)} \sum_{j=1}^{n_d^{(k)}}\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_{j}^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2 + 5\eta^2 n \widehat{L}^{(k)} \sum_{j=n_d^{(k)}+1}^{n}\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)}( {\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}})\Big\|^2 \\ \nonumber &\quad + 10 \eta^2 n^2 \widehat{L}^{(k)} L B_F({\mathbf{z}}, {\mathbf{x}}^*) + 5 \eta^2 \frac{1}{n} \Big(\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 \Big)\\ \nonumber &\quad + 5\eta^2 \frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2\Big)\\ \nonumber &\quad + 5\eta^2 L^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2\\ \nonumber &\quad - \frac{1}{n} \Big( \sum_{i=1}^{n_d^{(k)}} \frac{ \left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2}{2 L_{\pi_{i}^{(k)}}} + \sum_{i=n_d^{(k)}+1}^{n} \frac{\left\| \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \right\|^2}{2\widetilde{L}_{i-n_d^{(k)}}^{(k)}} \Big) \end{align}\]

If one sets the learning rate \(\eta\) such that \[\begin{align} &5 \eta^2 n \widehat{L}^{(k)} \leq \frac{1}{n} \cdot \frac{1}{2 \widehat{L}^{(k)*}}, \quad \Rightarrow \eta \leq \frac{1}{n\sqrt{10 \widehat{L}^{(k)} \widehat{L}^{(k)*}}} \end{align}\] then there is \[\begin{align} &\frac{1}{n} \Big(\sum_{i=1}^{n_d^{(k)}} \Big( B_{f_{\pi_i^{(k)}}}({\mathbf{x}}_{1}^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{\pi_i^{(k)}}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) + \sum_{i=n_d^{(k)}+1}^{n}\Big( B_{f_{i-n_d^{(k)}}^{(k,pub)}}({\mathbf{x}}_1^{(k+1)}, {\mathbf{x}}_i^{(k)}) - B_{f_{i-n_d^{(k)}}^{(k, pub)}}({\mathbf{z}}, {\mathbf{x}}_i^{(k)}) \Big) \Big) \\ \nonumber &\leq \widehat{L}^{(k)} \|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)} \|^2 + 10\eta^2 n^2 \widehat{L}^{(k)} L B_F({\mathbf{z}}, {\mathbf{x}}^{*})\\ \nonumber &\quad + 5 \eta^2 \frac{1}{n} \Big(\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 \Big)\\ \nonumber &\quad + 5\eta^2 \frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2\Big)\\ &\quad + 5\eta^2 L^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \end{align}\] ◻

Proof of Lemma 11. By Lemma 9 and Lemma 10, for any \(k \in [K]\) and \(\forall {\mathbf{z}}\in \mathbb{R}^d\), if \(\eta \leq \frac{1}{n\sqrt{10 \widehat{L}^{(k)} \widehat{L}^{(k)*}}}\), \[\begin{align} \label{eq:one95epoch95convergence95interm} &G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}})\\ \nonumber &\leq H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}}) + \frac{\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2}{2n \eta} - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 - \frac{1}{2n \eta}\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\\ \nonumber &\quad + \frac{1}{n}\sum_{i=1}^{n}\langle -\rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle + \widehat{L}^{(k)} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 + 10\eta^2 n^2 \widehat{L}^{(k)} L B_F({\mathbf{z}}, {\mathbf{x}}^*) \\ \nonumber &\quad + 5 \eta^2 \frac{1}{n} \Big(\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 \Big)\\ \nonumber &\quad + 5\eta^2 \frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2\Big)\\ \nonumber &\quad + 5\eta^2 L^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)} + 1}^{n} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \end{align}\tag{27}\]

Since \(\eta \leq \frac{1}{n \sqrt{10 \widehat{L}^{(k)} \widehat{L}^{(k)*}}}\), there is \(\widehat{L}^{(k)} \leq \sqrt{\widehat{L}^{(k)} \widehat{L}^{(k)*}} \leq \frac{1}{\sqrt{10} n \eta} \leq \frac{1}{2 n \eta}\), and so \((\widehat{L}^{(k)} - \frac{1}{2n \eta})\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \leq 0\).

For any \(\beta > 0\) and any \({\mathbf{z}}\in\mathbb{R}^{d}\), \[\begin{align} \nonumber &H^{(k)}({\mathbf{x}}_{1}^{(k+1)}) - H^{(k)}({\mathbf{z}})\\ \nonumber &= H^{(k)}({\mathbf{x}}_{1}^{(k+1)}) - H^{(k)}({\mathbf{z}}) - \langle \nabla H^{(k)}({\mathbf{z}}), {\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\rangle + \langle \nabla H^{(k)}({\mathbf{z}}), {\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\rangle\\ \nonumber &\stackrel{\text{(a)}}{\leq} \frac{L_H^{(k)}}{2} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\|^2 + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + \frac{\beta}{2} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\|^2 \\ \label{eq:dissim95ub} &= \frac{L_H^{(k)} + \beta}{2} \|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\|^2 + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 \end{align}\tag{28}\] where (a) is by Assumption 5, 6, Lemma 6 and Young’s inequality.

We comment that if \(H^{(k)} = 0\) for epoch \(s\), a tighter bound \(H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}}) = 0\) holds, as Young’s inequality is not tight in this case. Consequently, one can set \(\beta = 0\).

Finally, plugging Eq.@eq:eq:dissim95ub back to Eq.@eq:eq:one95epoch95convergence95interm yields the inequality (?? ) stated in the lemma. ◻

Proof of Lemma 12. First, note that if \({\mathbf{z}}\) is independent of \(\rho_i^{(k)}\), \(\forall i\in [n]\), there is

\(\mathbb{E}\left[\langle \frac{1}{n}\sum_{i=1}^{n} \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \right] = \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[ \langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \right] = \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[ \langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} \rangle \right]\).

Recall that the update rule in Algorithm 1 in epoch \(k\in [K]\) is \[\begin{align} \nonumber &{\mathbf{x}}_{i+1}^{(k)} = {\mathbf{x}}_{i}^{(k)} - \eta \Big(\nabla f_{\pi_i^{(k)}} + \rho_i^{(k)}\Big),\quad \forall i \in[n_d^{(k)}]\\ \nonumber &{\mathbf{x}}_{i+1}^{(k)} = {\mathbf{x}}_i^{(k)} - \eta \Big(\nabla f_{i-n_d^{(k)}}^{(k, pub)} + \rho_i^{(k)}\Big), \quad \forall n_d^{(k)} < i \leq n\\ \label{eq:prox95step} &{\mathbf{x}}_{1}^{(k+1)} = \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in\mathbb{R}^d} n \psi({\mathbf{x}}) + \frac{\| {\mathbf{x}}- {\mathbf{x}}_{n+1}^{(k)}\|^2}{2\eta} \end{align}\tag{29}\]

Since \(\psi\) is twice differentiable, by Stein’s Lemma (Lemma 5), for any \(i\in [n]\), conditional on \(\rho_j^{(k)}, \forall j\neq i\), \[\begin{align} \label{eq:application95steins95lemma} \mathbb{E}_{\rho_i^{(k)}}\left[ \langle \rho_i^{(k)}, {\mathbf{x}}_{1}^{(k+1)} \rangle \mid \{\rho_j^{(k)}\}_{j\neq i}\right] = (\sigma^{(k)})^2\cdot \mathbb{E}_{\rho_i^{(k)}}\left[\text{tr}(\frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}}) \mid \{\rho_j^{(k)}\}_{j\neq i} \right] \end{align}\tag{30}\] We proceed by computing \(\frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}}\). By the optimality condition of \({\mathbf{x}}_1^{(k+1)}\) as in Eq. 29 ,

\[\begin{align} &n \nabla \psi({\mathbf{x}}_1^{(k+1)}) + \frac{1}{\eta}\cdot ({\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_{n+1}^{(k)}) = \mathbf{0}\\ &n\eta \nabla \psi({\mathbf{x}}_1^{(k+1)}) + {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_{n+1}^{(k)} = \mathbf{0} \end{align}\]

And using implicit differentiation of the above optimality condition, \[\begin{align} \nonumber &n \eta \frac{\partial \nabla \psi({\mathbf{x}}_1^{(k+1)})}{\partial \rho_i^{(k)}} + \frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}} - \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} = \mathbf{0}\\ \nonumber &n \eta \nabla^2\psi({\mathbf{x}}_1^{(k+1)})\frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}} + \frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}} - \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} = \mathbf{0}\\ \nonumber &\Big( n \eta \nabla^2 \psi({\mathbf{x}}_1^{(k+1)}) + {\mathbb{I}}_d \Big) \frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}} = \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}}\\ \label{eq:diff95implicit} &\frac{\partial {\mathbf{x}}_{1}^{(k+1)}}{\partial \rho_i^{(k)}} = \Big(\eta n \nabla^2 \psi({\mathbf{x}}_1^{(k+1)}) + {\mathbb{I}}_d \Big)^{-1} \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \end{align}\tag{31}\] where \(\nabla^2 \psi({\mathbf{x}}_1^{(k+1)})\) is the Hessian of \(\psi\) evaluated at \({\mathbf{x}}_1^{(k+1)}\).

We proceed by computing \(\frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}}\). Note that \(\rho_i^{(k)}\) directly affects the update of \({\mathbf{x}}_{i+1}^{(k)}\) and indirectly affects the subsequent updates of \({\mathbf{x}}_{j}^{(k)}\) for all \(j > i + 1\). Hence, we decompose \({\mathbf{x}}_{n+1}^{(k)}\) as follows: for \(i \leq n_d^{(k)}\), \[\begin{align} {\mathbf{x}}_{n+1}^{(k)} &= \underbrace{ {\mathbf{x}}_1 - \eta \sum_{j=1}^{i-1}\Big( \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)} \Big) - \nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) }_{\text{Independent of \rho_i^{(k)}}}\\ \nonumber &\quad - \underbrace{ \rho_i^{(k)} }_{\text{Direct dependency}} - \underbrace{ \eta \sum_{j=i+1}^{n_d^{(k)}}\Big( \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}\Big) - \eta \sum_{j=n_d^{(k)}+1}^{n}\Big(\nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)} \Big) }_{\text{Implicit dependency on \rho_i^{(k)} through {\mathbf{x}}_j^{(k)}'s}} \end{align}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} {\mathbf{x}}_{n+1}^{(k)} &= \underbrace{ {\mathbf{x}}_1 - \eta \sum_{j=1}^{n_d^{(k)}} \Big(\nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}\Big) - \eta \sum_{j=n_d^{(k)}+1}^{i-1}\Big(\nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}\Big) - \nabla f_i^{(k, pub)}({\mathbf{x}}_i^{(k)}) }_{\text{Independent of \rho_i^{(k)} through {\mathbf{x}}_j^{(k)}'s}}\\ \nonumber &\quad - \underbrace{\rho_i^{(k)}}_{\text{Direct dependency}} - \underbrace{ \eta \sum_{j=i+1}^{n}\Big(\nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)}\Big) }_{\text{Implicit dependency on \rho_i^{(k)}}} \end{align}\] And so for \(i\leq n_d^{(k)}\), \[\begin{align} \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \nonumber &= -\eta {\mathbb{I}}_d - \eta \sum_{j=i+1}^{n_d^{(k)}} \frac{\partial \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)})}{\partial \rho_i^{(k)}} - \eta \sum_{j=n_d^{(k)}+1}^{n} \frac{\partial \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)})}{\partial \rho_i^{(k)}}\\ \label{eq:partial95x95n195small95i} &= -\eta {\mathbb{I}}_d - \eta \sum_{j=i+1}^{n_d^{(k)}} \nabla^2 f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)})\frac{\partial {\mathbf{x}}_j^{(k)}}{\partial \rho_i^{(k)}} - \eta \sum_{j=n_d^{(k)}+1}^{n} \nabla^2 f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) \frac{\partial {\mathbf{x}}_j^{(k)}}{\partial \rho_i^{(k)}} \end{align}\tag{32}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} \label{eq:partial95x95n195large95i} \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} = -\eta {\mathbb{I}}_d - \eta \sum_{j=i+1}^{n}\frac{\partial \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)})}{\partial \rho_i^{(k)}} = -\eta {\mathbb{I}}_d - \eta \sum_{j=i+1}^{n} \nabla^2 f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) \frac{\partial {\mathbf{x}}_j^{(k)}}{\partial \rho_i^{(k)}} \end{align}\tag{33}\]

We now compute \(\frac{\partial {\mathbf{x}}_j^{(k)}}{\partial \rho_i^{(k)}}\) for \(j > i\). First, note that by the update rule, \[\begin{align} \label{eq:partial95x95i1} \frac{\partial {\mathbf{x}}_{i+1}^{(k)}}{\partial \rho_i^{(k)}} = -\eta {\mathbb{I}}_d \end{align}\tag{34}\]

and for any \(i < j \leq n\), \[\begin{align} &\frac{\partial {\mathbf{x}}_{j+1}^{(k)}}{\partial \rho_i^{(k)}} = \begin{cases} \frac{\partial}{\partial \rho_i^{(k)}}\Big({\mathbf{x}}_{j}^{(k)} - \eta \Big(\nabla f_{\pi_{j}^{(k)}}({\mathbf{x}}_{j}^{(k)}) + \rho_{j}^{(k)} \Big) \Big) & \text{if j\leq n_d^{(k)}}\\ \frac{\partial}{\partial \rho_i^{(k)}}\Big({\mathbf{x}}_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_{j}^{(k)}) + \rho_{j}^{(k)} \Big) & \text{Otherwise} \end{cases}\\ &\Rightarrow \frac{\partial {\mathbf{x}}_{j+1}^{(k)}}{\partial \rho_i^{(k)}} = \begin{cases} \Big({\mathbb{I}}_d - \eta \nabla^2 f_{\pi_{j}^{(k)}}({\mathbf{x}}_{j}^{(k)})\Big) \frac{\partial {\mathbf{x}}_{j}^{(k)}}{\partial \rho_i^{(k)}} & \text{if j \leq n_d^{(k)}}\\ \Big( {\mathbb{I}}_d - \eta \nabla^2 f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_{j}^{(k)})\Big)\frac{\partial {\mathbf{x}}_{j}^{(k)}}{\partial \rho_i^{(k)}} & \text{Otherwise} \end{cases} \end{align}\] Therefore, by the above recursion, for any \(i < j \leq n_d^{(k)}\), \[\begin{align} \label{eq:partial95x95j95small95i} \frac{\partial {\mathbf{x}}_{j+1}^{(k)}}{\partial \rho_i^{(k)}} = -\eta \cdot \prod_{l=i+1}^{j}\Big( {\mathbb{I}}_d - \eta \nabla^2 f_{\pi_{l}^{(k)}}({\mathbf{x}}_{l}^{(k)})\Big) \end{align}\tag{35}\] and similarity, for any \(n_d^{(k)} < j \leq n\), \[\begin{align} \label{eq:partial95x95j95large95i} \frac{\partial {\mathbf{x}}_{j+1}^{(k)}}{\partial \rho_i^{(k)}} = -\eta \cdot \Big(\prod_{l=i+1}^{n_d^{(k)}}\Big({\mathbb{I}}_d - \eta \nabla^2 f_{\pi_{l}^{(k)}}({\mathbf{x}}_{l}^{(k)})\Big) \Big)\cdot \Big(\prod_{l=n_d^{(k)}+1}^{j} \Big({\mathbb{I}}_d - \eta \nabla^2 f_{l-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_{l}^{(k)}) \Big) \Big) \end{align}\tag{36}\]

Therefore, plugging Eq. 34 , Eq. 35 and Eq. 36 back to Eq. 32 or Eq. 33 , there is, for \(i \leq n_d^{(k)}\),

\[\begin{align} &\frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} = -\eta {\mathbb{I}}_d + \eta^2 \nabla^2 f_{\pi_{i+1}^{(k)}}({\mathbf{x}}_{i+1}^{(k)}) + \eta^2 \sum_{j=i+2}^{n_d^{(k)}} \nabla^2 f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) \prod_{l=i+1}^{j-1} \Big( {\mathbb{I}}_d - \eta \nabla^2 f_{\pi_l^{(k)}}({\mathbf{x}}_{l}^{(k)})\Big)\\ \nonumber &\quad + \eta^2 \nabla^2 f_{1}^{(k, pub)}({\mathbf{x}}_{n_d^{(k)}+1}^{(k)}) \prod_{l=i+1}^{n_d^{(k)}}\Big( {\mathbb{I}}_d - \eta \nabla^2 f_{\pi_l^{(k)}}({\mathbf{x}}_l^{(k)})\Big)\\ \nonumber &\quad + \eta^2 \sum_{j=n_d^{(k)}+2}^{n} \nabla^2 f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_j^{(k)}) \Big(\prod_{l=i+1}^{n_d^{(k)}}\Big({\mathbb{I}}_d - \eta\nabla^2 f_{\pi_l^{(k)}}({\mathbf{x}}_l^{(k)})\Big)\Big) \cdot\Big( \prod_{l=n_d^{(k)}+1}^{j-1}\Big({\mathbb{I}}_d - \eta \nabla f_{l-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_l^{(k)}) \Big) \Big) \end{align}\] and for \(n_d^{(k)} < i \leq n\), \[\begin{align} \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} &= -\eta {\mathbb{I}}_d + \eta^2 \nabla^2 f_{i+1-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_{i+1}^{(k)}) + \eta^2 \sum_{j=i+2}^{n} \nabla^2 f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_j^{(k)})\\ \nonumber &\quad \cdot \Big(\prod_{i+1}^{n_d^{(k)}}\Big({\mathbb{I}}_d - \eta \nabla^2 f_{\pi_k^{(k)}}({\mathbf{x}}_k^{(k)}) \Big)\Big) \cdot \Big(\prod_{l=n_d^{(k)}+1}^{j-1} \Big({\mathbb{I}}_d - \eta \nabla f_{l-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_l^{(k)}) \Big) \end{align}\] By Assumption 1 and 2, \(\|\nabla^2 f_i({\mathbf{x}})\|_{op} \leq \widehat{L}^{(k)*}\) and \(\|\nabla^2 f_{j}^{(k,pub)}({\mathbf{x}})\|_{op} \leq \widehat{L}^{(k)*}\), \(\forall i\in [n_d^{(k)}], j\in[n-n_d^{(k)}]\) and \(\forall {\mathbf{x}}\in\mathbb{R}^d\), where \(\|\cdot\|_{op}\) denotes the matrix operator norm and recall that \(\widehat{L}^{(k)*} = \max\{ \{L_{\pi_i^{(k)}}\}_{i=1}^{n_d^{(k)}} \cup \{\widetilde{L}^{(k)}_i\}_{i=1}^{n-n_d^{(k)}} \}\) is the maximum smoothness parameter in epoch \(k\).

And so if \(\eta \leq \frac{1}{\widehat{L}^{(k)*}}\), \(\forall i \in [n]\), \[\begin{align} \label{eq:op95ub} \left\| \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} \leq n \eta^2 \widehat{L}^{(k)*} \end{align}\tag{37}\]

Moreover, by Assumption 4, \(\lambda_{min}(\nabla^2 \psi({\mathbf{x}})) \geq 0\), \(\forall {\mathbf{x}}\in \mathbb{R}^d\), where \(\lambda_{min}\) denotes the minimum eigenvalue. And so \[\begin{align} \left\| \Big({\mathbb{I}}_d + \eta n \nabla^2 \psi({\mathbf{x}}_1^{(k+1)})\Big)^{-1} \right\|_{op} \leq 1 \end{align}\] Hence, by Eq. 31 , \[\begin{align} \left\| \frac{\partial {\mathbf{x}}_{1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} = \left\| \Big(\eta n \nabla^2 \psi({\mathbf{x}}_1^{(k+1)}) + {\mathbb{I}}_d \Big)^{-1} \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} \leq n\eta^2 \widehat{L}^{(k)*} \end{align}\] Since for some symmetric real matrix \({\boldsymbol{A}}\), \(\text{tr}({\boldsymbol{A}}) \leq d \|{\boldsymbol{A}}\|_{op}\), \[\begin{align} \text{tr}(\frac{\partial {\mathbf{x}}_{1}^{(k+1)}}{\partial \rho_i^{(k)}}) \leq nd \eta^2 \widehat{L}^{(k)*} \end{align}\] Hence, by Eq. 30 , for any \(i\in [n]\), conditional on \(\rho_j^{(k)}, \forall j\neq i\), \[\begin{align} \mathbb{E}_{\rho_i^{(k)}}\left[ \langle \rho_i^{(k)}, {\mathbf{x}}_{1}^{(k+1)} \rangle \mid\{\rho_j^{(k)}\}_{j\neq i} \right] = (\sigma^{(k)})^2\cdot \mathbb{E}_{\rho_i^{(k)}}\left[\text{tr}(\frac{\partial {\mathbf{x}}_1^{(k+1)}}{\partial \rho_i^{(k)}}) \mid\{\rho_j^{(k)}\}_{j\neq i} \right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} \end{align}\] and by law of total expectation, \[\begin{align} \mathbb{E}\left[\langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)}\rangle \right] = \mathbb{E}\left[ \mathbb{E}_{\rho_i^{(k)}}\left[ \langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)}\rangle \mid \{\rho_j\}_{j\neq i} \right] \right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} \end{align}\] and so \[\begin{align} \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n} \langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} \end{align}\] ◻

Proof of Lemma 13. First, note that \(\rho_i^{(k)}\) and \(\rho_j^{(k)}\), i.e., the noise injected at step \(i\) and step \(j\) in epoch \(k\), are independent, for any \(i \neq j\). Thus, \[\begin{align} \mathbb{E}\left[ \Big\|\sum_{j=1}^{i} \rho_j^{(k)} \Big\|^2 \right] &= \sum_{j=1}^{i}\mathbb{E}\left[\Big\| \rho_j^{(k)}\Big\|^2\right] + 2 \sum_{j=1}^{i} \sum_{k=j+1}^{i} \mathbb{E}\left[\langle \rho_i^{(k)}, \rho_j^{(k)}\rangle \right]\\ &= \sum_{j=1}^{i}\mathbb{E}\left[\Big\| \rho_j^{(k)}\Big\|^2\right]\\ &\leq i d (\sigma^{(k)})^2 \end{align}\] ◻

Proof of 14. By Assumption 6, \[\begin{align} \label{eq:exp95dissimilarity} &\frac{1}{n} \sum_{i=n_d^{(k)} + 1}^{n} \mathbb{E}_{\pi^{(k)}} \Big\| \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \leq \frac{1}{n}\sum_{i=n_d^{(k)} + 1}^{n-1} (C_i^{(k)})^2 \end{align}\tag{38}\]

and by Lemma 7, for any permutation \(\pi^{(k)}\in \Pi_{n}\), there is \[\begin{align} \label{eq:exp95opt95uncertainty} &\mathbb{E}_{\pi^{(k)}} \Big[\frac{1}{n} \Big(\sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n}\widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1}\nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*)\Big\|^2 \Big)\Big] \leq n^2 \widehat{L}^{(k)} \sigma_{any}^2 \end{align}\tag{39}\]

where the expectation is taken w.r.t. the shuffling operator \(\pi^{(k)}\).

Moreover, by Lemma 13, \[\begin{align} \nonumber &\mathbb{E}_{\pi^{(k)}}\Big[\frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} \Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)}\Big\| \sum_{j=1}^{i-1} \rho_j^{(k)}\Big\|^2\Big)\Big]\\ \nonumber &\leq \frac{1}{n} \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} (i-1) d(\sigma^{(k)})^2 + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} (i-1) d (\sigma^{(k)})^2\Big)\\ \label{eq:exp95noise} &\leq \frac{1}{n} nd (\sigma^{(k)})^2 \Big( \sum_{i=2}^{n_d^{(k)}} L_{\pi_i^{(k)}} + \sum_{i=n_d^{(k)}+1}^{n} \widetilde{L}_{i-n_d^{(k)}}^{(k)} \Big) \leq nd (\sigma^{(k)})^2 \widehat{L}^{(k)} \end{align}\tag{40}\]

where the expectation is taken w.r.t. the injected noise \(\{\rho_j^{(k)}\}_{j=1}^{n}\).

Following Eq. 38 , 39 , 40 , and Lemma 11, 12, for any \({\mathbf{z}}\in\mathbb{R}^{d}\),

\[\begin{align} &\mathbb{E}\left[ G({\mathbf{x}}_1^{(k+1)})\right] - \mathbb{E}\left[ G({\mathbf{z}}) \right]\\ \nonumber &\leq \frac{1}{2 n \eta}\Big( \mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2\right] - \mathbb{E}\left[ \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 \right] \Big) + \Big( \frac{L_H^{(k)} + \beta}{2} - \frac{\mu_{\psi}}{2} \Big) \mathbb{E}\left[\| {\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 \right]\\ \nonumber &\quad + 10\eta^2 n^2 \widehat{L}^{(k)} L \mathbb{E}\left[ B_F({\mathbf{z}}, {\mathbf{x}}^*)\right] + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5\eta^2 \widehat{L}^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)} + 1}^{n-1}(C_i^{(k)})^2 + 5 \eta^2 n^2 \widehat{L}^{(k)}\sigma_{any}^2 \\ \nonumber &\quad + \eta^2 (\sigma^{(k)})^2 nd \widehat{L}^{(k)*} + 5\eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)} \end{align}\] where the expectation is taken w.r.t. both the injected noise within epoch \(k\), i.e., \(\{\rho_i^{(k)}\}_{i=1}^{n}\), and the shuffling operator \(\pi^{(k)}\). Combining the last two terms and note that \(\widehat{L}^{(k)} \leq \widehat{L}^{(k)*}\) yields the inequality (?? ) in the above lemma statement. ◻

Proof of Lemma 15. Fix an arbitrary number of epochs \(s\in [K]\).

If \(\mu_\psi \geq L_H^{(k)} + \beta\), \(\forall k\in [s]\), \(\eta \leq \frac{1}{n\sqrt{10 \max_{k\in [s]} (\widehat{L}^{(k)} \widehat{L}^{(k)*}})}\), and \({\mathbf{z}}\) independent of \(\{\rho_i^{(k)}\}_{i=1}^{n}\), then by Lemma 14, for any \(k\in [s]\), \[\begin{align} \label{eq:expected95one95epoch95convergence95strong95reg} &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)})\right] - \mathbb{E}\left[G({\mathbf{z}})\right]\\ \nonumber &\leq \frac{1}{2 n \eta}\Big( \mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2\right] - \mathbb{E}\left[ \|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 \right] \Big) + 10\eta^2 n^2 \widehat{L}^{(k)} L \mathbb{E}\left[ B_F({\mathbf{z}}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5 \eta^2 n^2 \widehat{L}^{(k)}\sigma_{any}^2 + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5\eta^2 \widehat{L}^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2 + 6 \eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)*} \end{align}\tag{41}\]

Define the non-decreasing sequence \[\begin{align} v_k = \frac{1}{s+1-k}, \forall k\in [s], \quad v_0 = v_1 = \frac{1}{s} \end{align}\] and the auxiliary points \[\begin{align} \label{eq:z95def} {\mathbf{z}}^{(0)} = {\mathbf{x}}^*, \quad {\mathbf{z}}^{(k)} = \Big( 1- \frac{v_{k-1}}{v_k}\Big) {\mathbf{x}}_1^{(k)} + \frac{v_{k-1}}{v_k} {\mathbf{z}}^{(k-1)}, \forall k\in [s] \end{align}\tag{42}\] Equivalently, \({\mathbf{z}}^{(k)}\) can be re-written as \[\begin{align} \label{eq:z95eq95form} {\mathbf{z}}^{(k)} = \frac{v_0}{v_k}{\mathbf{x}}^* + \sum_{l=1}^{k} \frac{v_l - v_{l-1}}{v_k} {\mathbf{x}}_1^{(l)}, \forall k\in [0]\cup [s] \end{align}\tag{43}\]

Note that for an epoch \(k\), \({\mathbf{z}}^{(k)}\) only depends on \({\mathbf{x}}^*\) and \({\mathbf{x}}_1^{(l)}\), for \(l \leq k\), and hence by the update rule, \({\mathbf{z}}^{(k)}\) is independent of \(\rho_i^{(k)}\), \(\forall i\in [n]\). And so for any \(k\in [s]\), we can choose \({\mathbf{z}}= {\mathbf{z}}^{(k)}\) in Eq. 41 and this leads to

\[\begin{align} \label{eq:expected95one95epoch95convergence95strong95reg95z} &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)})\right] - \mathbb{E}\left[G({\mathbf{z}})\right]\\ \nonumber &\leq \frac{1}{2 n \eta}\Big( \mathbb{E}\left[\|{\mathbf{z}}^{(k)} - {\mathbf{x}}_1^{(k)}\|^2\right] - \mathbb{E}\left[ \|{\mathbf{z}}^{(k)} - {\mathbf{x}}_1^{(k+1)}\|^2 \right] \Big) + 10\eta^2 n^2 \widehat{L}^{(k)} L \mathbb{E}\left[ B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5 \eta^2 n^2 \widehat{L}^{(k)}\sigma_{any}^2 + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5\eta^2 \widehat{L}^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2 + 6 \eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)*} \end{align}\tag{44}\]

Note that by Eq. 42 , \[\begin{align} \|{\mathbf{z}}^{(k)} - {\mathbf{x}}_1^{(k)}\|^2 = \frac{v_{k-1}^2}{v_k^2} \| {\mathbf{z}}^{(k-1)} - {\mathbf{x}}_1^{(k)}\|^2 \leq \frac{v_{k-1}}{v_k}\|{\mathbf{z}}^{(k-1)} - {\mathbf{x}}_1^{(k)}\|^2 \end{align}\] where the last inequality is due to \(v_{k-1} \leq v_k\). Hence, following Eq. 44 ,

\[\begin{align} \label{eq:convergence95across95epochs95interm} &v_k \cdot \left(\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)})\right] - \mathbb{E}\left[G({\mathbf{z}})\right] \right)\\ \nonumber &\leq \frac{1}{2 n \eta}\Big( \mathbb{E}\left[ v_{k-1} \|{\mathbf{z}}^{(k-1)} - {\mathbf{x}}_1^{(k)}\|^2\right] - v_k \mathbb{E}\left[ \|{\mathbf{z}}^{(k)} - {\mathbf{x}}_1^{(k+1)}\|^2 \right] \Big) + 10 v_k \eta^2 n^2 \widehat{L}^{(k)} L \mathbb{E}\left[ B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5 v_k \eta^2 n^2 \widehat{L}^{(k)}\sigma_{any}^2 + v_k \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5 v_k \eta^2 \widehat{L}^{(k)*} \frac{1}{n} \sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2 + 6 v_k \eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)*} \end{align}\tag{45}\] Summing Eq. 45 from \(k = 1\) to \(s\) to obtain \[\begin{align} \label{eq:telescoping95sum95result} &\sum_{k=1}^{s} v_k \cdot \left(\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)})\right] - \mathbb{E}\left[G({\mathbf{z}})\right] \right) \leq \frac{1}{2 n \eta} \Big(\mathbb{E}\left[ v_0 \| {\mathbf{z}}^{(0)} - {\mathbf{z}}_1^{(1)}\|^2 \right] - v_{s}\mathbb{E}\left[\| {\mathbf{z}}^{(s)} - {\mathbf{x}}_1^{(s+1)}\|^2\right]\Big)\\ \nonumber &\quad + 10 \eta^2 n^2 L \sum_{k=1}^{s} \widehat{L}^{(k)} v_k \mathbb{E}\left[B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*)\right] + 5\eta^2 n^2 \sigma_{any}^2 \sum_{k=1}^{s} v_k \widehat{L}^{(k)} + \frac{1}{2n^2 \beta}\sum_{k=1}^{s} v_k (C_n^{(k)})^2\\ \nonumber &\quad + 5\eta^2 \sum_{k=1}^{s} v_k \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2 + 6\eta^2 nd \sum_{k=1}^{s} v_k (\sigma^{(k)})^2 \widehat{L}^{(k)*} \end{align}\tag{46}\]

Note since \(\|{\mathbf{z}}^{(s)} - {\mathbf{x}}_1^{(s+1)}\|^2 \geq 0\) and \({\mathbf{z}}^{(0)} = {\mathbf{x}}^*, v_0 = \frac{1}{s}\), \[\begin{align} \label{eq:convergence95across95epochs95tele95sum} \frac{1}{2\eta n}\Big( v_0 \mathbb{E}\left[ \| {\mathbf{z}}^{(0)} - {\mathbf{x}}_1^{(1)}\|^2 \right] - v_s \mathbb{E}\left[ \| {\mathbf{z}}^{(s)} - {\mathbf{x}}_1^{(s+1)} \|^2 \right] \Big) \leq \frac{1}{2\eta n s} \| {\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 \end{align}\tag{47}\]

We first bound the L.H.S. of Eq. 46 . By Assumption 1 and 4, the objective function \(G({\mathbf{x}}) = F({\mathbf{x}}) + \psi({\mathbf{x}})\) is convex, and hence, by Eq. 43 , there is \[\begin{align} G({\mathbf{z}}^{(k)}) \leq \frac{v_0}{v_k} G({\mathbf{x}}^*) + \sum_{l=1}^{k}\frac{v_l - v_{l-1}}{v_k} G({\mathbf{x}}_1^{(l)}) = G({\mathbf{x}}^*) + \sum_{l=1}^{k}\frac{v_l - v_{l-1}}{v_k} \Big( G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big) \end{align}\] which implies \[\begin{align} \nonumber &\sum_{k=1}^{s} v_k \Big( G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}}^{(k)})\Big)\\ \nonumber &\geq \sum_{k=1}^{s} \Big( v_k \Big(G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{x}}^*)\Big) - \sum_{l=1}^{k} (v_l - v_{l-1}) \Big(G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big) \Big)\\ \nonumber &\geq \sum_{k=1}^{s} v_k \Big(G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{x}}^*)\Big) - \sum_{k=1}^{s}\sum_{l=1}^{k} (v_l - v_{l-1}) \Big(G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big)\\ \nonumber &= \sum_{k=1}^{s} v_k \Big(G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{x}}^*)\Big) - \sum_{l=1}^{s}(s+1-l) (v_l - v_{l-1}) \Big(G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big)\\ \nonumber &= v_s \Big( G({\mathbf{x}}_1^{(s+1)}) - G({\mathbf{x}}^*) \Big) + \sum_{k=1}^{s-1} \frac{1}{s+1-k} \Big(G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{x}}^*)\Big)\\ \nonumber &\quad - s(v_1 - v_0)\Big( G({\mathbf{x}}_1^{(1)}) - G({\mathbf{x}}^*) \Big) - \sum_{l=2}^{s}(s+1-l)(\frac{1}{s+1-l} - \frac{1}{s+2-l})\Big(G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big)\\ \nonumber &= v_s \Big( G({\mathbf{x}}_1^{(s+1)}) - G({\mathbf{x}}^*) \Big) + \sum_{k=2}^{s} \frac{1}{s+2-k} \Big( G({\mathbf{x}}_1^{(k)}) - G({\mathbf{x}}^*) \Big)\\ \nonumber &\quad - s(v_1 - v_0) \Big( G({\mathbf{x}}_1^{(1)}) - G({\mathbf{x}}^*)\Big) - \sum_{l=2}^{s}\frac{1}{s+2-l}\Big(G({\mathbf{x}}_1^{(l)}) - G({\mathbf{x}}^*)\Big)\\ \nonumber &= v_s \Big( G({\mathbf{x}}_1^{(s+1)}) - G({\mathbf{x}}^*) \Big) - s(v_1 - v_0)\Big( G({\mathbf{x}}_1^{(1)}) - G({\mathbf{x}}^*)\Big) \end{align}\] Note that \(v_1 = v_0\) and \(v_s = 1\) by definition, and so taking expectation of both sides, \[\begin{align} \label{eq:convergence95across95arbitrary95epochs95lhs} \sum_{k=1}^{s} v_k\Big( \mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)}) \right] - \mathbb{E}\left[G({\mathbf{z}}^{(k)})\right]\Big) \geq \mathbb{E}\left[G({\mathbf{x}}_1^{(s+1)})\right] - G({\mathbf{x}}^*) \end{align}\tag{48}\]

We now bound the term involving \(\mathbb{E}\left[B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*)\right]\) in the R.H.S. of Eq. 46 . By the convexity of \(B_F(\cdot, {\mathbf{x}}^*)\) fixing the second argument (due to \(F\) being convex), and Eq. 43 , \[\begin{align} B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*) \leq \frac{v_0}{v_k}B_F({\mathbf{x}}^*, {\mathbf{x}}^*) + \sum_{l=1}^{k}\frac{v_l - v_{l-1}}{v_k}B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*) = \sum_{l=1}^{k}\frac{v_l - v_{l-1}}{v_k}B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*) \end{align}\] which implies \[\begin{align} \nonumber &10 \eta^2n^2 L \sum_{k=1}^{s} v_k \widehat{L}^{(k)} \mathbb{E}\left[B_F({\mathbf{z}}^{(k)}, {\mathbf{x}}^*)\right] \leq 10 \eta^2 n^2 L \max_{k\in[s]}\widehat{L}^{(k)} \sum_{k=1}^{s} \sum_{l=1}^{k} (v_l - v_{l-1})\mathbb{E}\left[B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*)\right]\\ \nonumber &= 10 \eta^2 n^2 L \max_{k\in[s]}\widehat{L}^{(k)} \sum_{l=1}^{s} (s+1-l)(v_l - v_{l-1}) \mathbb{E}\left[B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*)\right] \\ \nonumber &= 10 \eta^2 n^2 L \max_{k\in[s]}\widehat{L}^{(k)} \sum_{l=2}^{s} (s+1-l)(\frac{1}{s+1-l} - \frac{1}{s+2-l}) \mathbb{E}\left[B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*)\right] \\ \nonumber &= 10 \eta^2 n^2 L \max_{k\in[s]}\widehat{L}^{(k)} \sum_{l=2}^{s} \frac{1}{s+2-l} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*)\right]\\ \label{eq:convergence95across95epochs95bregmandiv} &= 10 \eta^2 n^2 L \max_{k\in[s]}\widehat{L}^{(k)} \sum_{l=2}^{s} v_{l-1} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(l)}, {\mathbf{x}}^*)\right] \end{align}\tag{49}\]

Therefore, plugging Eq. 47 , Eq. 48 and Eq. 49 back to Eq. 46 , there is, for any fixed epoch \(s\in [K]\) \[\begin{align} &\mathbb{E}\left[G({\mathbf{x}}_1^{(s+1)})\right] - G({\mathbf{x}}^*)\\ \nonumber &\leq \frac{1}{2\eta n s} \| {\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 + 10 \eta^2 n^2 L\max_{k\in[s]}\widehat{L}^{(k)} \sum_{k=2}^{s} \frac{1}{s+2-k} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5\eta^2 n^2 \sigma_{any}^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)} }{s+1-k} + \frac{1}{2n^2 \beta}\sum_{k=1}^{s} \frac{ (C_n^{(k)})^2 }{s+1-k}\\ \nonumber &\quad + 5\eta^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2}{s+1-k} + 6\eta^2 nd \sum_{k=1}^{s} \frac{ (\sigma^{(k)})^2 \widehat{L}^{(k)*} }{s+1-k} \end{align}\] ◻

Proof of Theorem 3. Taking the learning rate \(\eta \leq \frac{1}{2n \sqrt{20 \bar{L}^* \max_{k \in [K]}\widehat{L}^{(k)*} (1+\log K)}}\), where \(\bar{L}^* = \max\{L, \max_{k\in[K]} \widehat{L}^{(k)}\}\), i.e., the max average smoothness parameters, satisfies the condition of Lemma 15, and so for any number of epochs \(s \in [K]\), \[\begin{align} &\mathbb{E}\left[G({\mathbf{x}}_1^{(s+1)})\right] - G({\mathbf{x}}^*) \leq \frac{1}{2\eta n s} \| {\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 + 10 \eta^2 n^2 L\max_{k\in[s]}\widehat{L}^{(k)} \sum_{k=2}^{s} \frac{1}{s+2-k} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5\eta^2 n^2 \sigma_{any}^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)} }{s+1-k} + \frac{1}{2n^2 \beta}\sum_{k=1}^{s} \frac{ (C_n^{(k)})^2 }{s+1-k}\\ \nonumber &\quad + 5\eta^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2}{s+1-k} + 6\eta^2 nd \sum_{k=1}^{s} \frac{ (\sigma^{(k)})^2 \widehat{L}^{(k)*} }{s+1-k} \end{align}\]

Note that \(\sum_{k=1}^{s} v_k = \sum_{k=1}^{s} \frac{1}{s+1-k} = \sum_{k=1}^{s} \frac{1}{k}\leq 1+\log s\), and so \[\begin{align} 5 \eta^2 n^2 \sigma_{any}^2 \sum_{k=1}^{s} \frac{\widehat{L}^{(k)}}{s+1-k} \leq \eta^2 n^2 \sigma_{any}^2 (1+\log s) \max_{k\in [s]} \widehat{L}^{(k)} \end{align}\] Hence, \[\begin{align} &\mathbb{E}\left[G({\mathbf{x}}_1^{(s+1)})\right] - G({\mathbf{x}}^*) \leq \frac{1}{2\eta n s} \| {\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 + 10 \eta^2 n^2 L\max_{k\in[s]}\widehat{L}^{(k)} \sum_{k=2}^{s} \frac{1}{s+2-k} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5\eta^2 n^2 \sigma_{any}^2 (1+\log s) \max_{k\in [s]}\widehat{L}^{(k)} + \frac{1}{2n^2 \beta}\sum_{k=1}^{s} \frac{ (C_n^{(k)})^2 }{s+1-k}\\ \nonumber &\quad + 5\eta^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2}{s+1-k} + 6\eta^2 nd \sum_{k=1}^{s} \frac{ (\sigma^{(k)})^2 \widehat{L}^{(k)*} }{s+1-k} \end{align}\]

By the optimality condition, \(\nabla G({\mathbf{x}}^*) = \nabla F({\mathbf{x}}^*) + \nabla \psi({\mathbf{x}}^*) = \mathbf{0}\). Thus, for any \(s\in [K]\), \[\begin{align} \mathbb{E}\left[G({\mathbf{x}}_1^{(s+1)})\right] - G({\mathbf{x}}^*) &\geq \mathbb{E}\left[ G({\mathbf{x}}_1^{(s+1)})\right] - \mathbb{E}\left[ G({\mathbf{x}}^*)\right] - \mathbb{E}\left[\langle \nabla F({\mathbf{x}}^*) + \nabla \psi({\mathbf{x}}^*), {\mathbf{x}}_1^{(s+1)} - {\mathbf{x}}^* \rangle \right] \\ &= \mathbb{E}\left[ B_F({\mathbf{x}}_1^{(s+1)},{\mathbf{x}}^*)\right] + \mathbb{E}\left[ B_{\psi}({\mathbf{x}}_1^{(s+1)}, {\mathbf{x}}^*)\right] \geq \mathbb{E}\left[ B_F({\mathbf{x}}_1^{(s+1)}, {\mathbf{x}}^*)\right] \end{align}\] which implies that for any \(s\in [K]\), \[\begin{align} &\mathbb{E}\left[B_F({\mathbf{x}}_1^{(s+1)}), {\mathbf{x}}^*)\right] \leq \frac{1}{2\eta n s} \| {\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 + 10 \eta^2 n^2 L\max_{k\in[s]}\widehat{L}^{(k)} \sum_{k=2}^{s} \frac{1}{s+2-k} \mathbb{E}\left[B_F({\mathbf{x}}_1^{(k)}, {\mathbf{x}}^*)\right]\\ \nonumber &\quad + 5\eta^2 n^2 \sigma_{any}^2 (1+\log s) \max_{k\in [s]}\widehat{L}^{(k)} + \frac{1}{2n^2 \beta}\sum_{k=1}^{s} \frac{ (C_n^{(k)})^2 }{s+1-k}\\ \nonumber &\quad + 5\eta^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2}{s+1-k} + 6\eta^2 nd \sum_{k=1}^{s} \frac{ (\sigma^{(k)})^2 \widehat{L}^{(k)*} }{s+1-k} \end{align}\] Note that \(\max_{k\in [s]}\widehat{L}^{(k)} \leq \max_{k\in [K]} \widehat{L}^{(k)}\).

Now we apply Lemma 8 with

• \(d^{(s+1)}=\begin{cases} \mathbb{E}\left[ B_F({\mathbf{x}}_1^{(s+1)}, {\mathbf{x}}^*)\right] &s \in [K-1]\\ \mathbb{E}\left[ F({\mathbf{x}}_1^{(K+1)}) \right] - \mathbb{E}\left[ F({\mathbf{x}}^*) \right] &s = K \end{cases}\)

• \(e^{(k)} = \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5\eta^2 \widehat{L}^{(k)*}\frac{1}{n}\sum_{i=1}^{n-1}(C_i^{(k)})^2 + 6\eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)*}, \forall k\in [K]\)

• \(a = \frac{1}{2\eta n}\| {\mathbf{x}}_1^{(1)} - {\mathbf{x}}^*\|^2\)

• \(b = 5\eta^2 n^2 \sigma_{any}^2(1+\log s) \max_{k\in [K]} \widehat{L}^{(k)}\)

• \(c = 10\eta^2 n^2 L \max_{k\in[K]} \widehat{L}^{(k)}\)

to obtain \[\begin{align} &\mathbb{E}\left[ G({\mathbf{x}}_1^{(K+1)}) \right] - G({\mathbf{x}}^*)\\ \nonumber &\leq \Big( \frac{1}{2\eta n K} \|{\mathbf{x}}^* - {\mathbf{x}}_1^{(1)}\|^2 + 5\eta^2 n^2 \sigma_{any}^2 (1+\log K)\max_{k\in[K]} \widehat{L}^{(k)} + M\Big) \sum_{i=0}^{K-1} \Big(20 \eta^2 n^2 L \max_{k\in [K]}\widehat{L}^{(k)}(1+\log K) \Big)^{i} \end{align}\] where \[\begin{align} M = \max_{s\in [K]} \Big( \frac{1}{2n^2 \beta}\sum_{k=1}^{s} \frac{ (C_n^{(k)})^2 }{s+1-k} + 5\eta^2 \sum_{k=1}^{s} \frac{ \widehat{L}^{(k)*} \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1}(C_i^{(k)})^2}{s+1-k} + 6\eta^2 nd \sum_{k=1}^{s} \frac{ (\sigma^{(k)})^2 \widehat{L}^{(k)*} }{s+1-k} \Big) \end{align}\]

By setting \(\eta \leq \frac{1}{2n \sqrt{10 \bar{L}^{*} \max_{k\in [K]}\widehat{L}^{(k)*} (1+\log K)}}\), where \(\bar{L}^{*} = \max\{L, \max_{k\in[K]} \widehat{L}^{(k)}\}\), there is \[\begin{align} \sum_{i=0}^{K-1} \Big(20 \eta^2 n^2 L \max_{k\in [K]}\widehat{L}^{(k)}(1+\log K) \Big)^{i} \leq \sum_{i=0}^{K-1} \Big( \frac{n^2 L \max_{k\in[K]}\widehat{L}^{(k)} (1+\log K)}{2 n^2 \bar{L}^* \max_{k\in[K]} \widehat{L}^{(k)*} (1+\log K)} \Big)^{i} \leq \sum_{i=0}^{\infty} \frac{1}{2^{i}} = 2 \end{align}\]

Therefore, \[\begin{align} &\mathbb{E}\left[ G({\mathbf{x}}_1^{(K+1)}) \right] - G({\mathbf{x}}^*) \leq \frac{\| {\mathbf{x}}_1^{(1)} - {\mathbf{x}}^*\|^2 }{\eta n K} + 10 \eta^2 n^2 \sigma_{any}^2 (1+\log K)\max_{k\in[K]} \widehat{L}^{(k)} + 2 M \end{align}\] ◻

Proof of Corollary 2. The convergence bound in Eq. ?? follows directly from the general result in Theorem 3 (Eq. ?? ) by setting: the number of private samples per epoch \(n_d^{(k)} = n\), dissimilarity \(C_n^{(k)} = 0\), noise \(\sigma^{(k)} = 0\), and using the appropriate smoothness constants—maximum \(L^{*} = \max_{i\in[n]} L_i\) and average per epoch \(\widehat{L}^{(k)} = \frac{1}{n} \sum_{i=1}^{n} L_i = L\) for all \(k \in [K]\). With these settings, Eq. ?? recovers the convergence bound for non-private shuffled gradient methods under smooth objectives prior to specifying the learning rate \(\eta\), as shown in Theorem C.1 of [11]. Adopting the same learning rate choice as in [11] yields the exact result stated in their Theorem 4.4 and full version Theorem C.1. ◻

Proof of Lemma 16. We first show the privacy loss per epoch by using privacy amplification by iteration (PABI) in Renyi Differential Privacy (RDP, see Definition 4), and then use the composition theorem of RDP (see Proposition 3) to derive the total privacy loss across \(K\) epochs. Finally, we convert the privacy loss in RDP to DP based on Proposition 2.

By Remark 4, if one sets the learning rate in \(\textit{DP-ShuffleG}\) as \(\eta \leq 1/L^{*}\), each gradient update step in epoch \(k \in [K]\), i.e., \({\mathbf{x}}_{i+1}^{(k)} = {\mathbf{x}}_{i}^{(k)} - \eta (\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i^{(k)}) + \rho_i^{(k)} )\), \(\forall i\in [n]\), (line 8 of Algorithm 1) satisfies a “noisy contractive sequence” (CNI, see Definition 6) and hence, we can apply Theorem 2 to reason about the privacy loss of epoch \(k\), \(\forall k\in[K]\).

Let \({\mathsf{D}}= \{{\mathbf{d}}_1, \dots, {\mathbf{d}}_t, \dots, {\mathbf{d}}_n\}\) and \({\mathsf{D}}' = \{{\mathbf{d}}_1, \dots, {\mathbf{d}}_{t}', \dots, {\mathbf{d}}_n\}\) be two neighboring datasets that differ at some index \(t \in [n]\). On dataset \({\mathsf{D}}\), the CNI is defined by the initial point \({\mathbf{x}}_1^{(k)}\), sequence of functions \(g_i({\mathbf{x}}) = {\mathbf{x}}_i^{(k)} - \eta \nabla f({\mathbf{x}}; {\mathbf{d}}_{\pi_i^{(k)}})\), for all \({\mathbf{x}}\), and sequence of noise distributions \({\mathcal{N}}(0, (\eta \sigma)^2 {\mathbb{I}}_d)\). Similarly, on dataset \({\mathsf{D}}'\), the CNI is defined in the same way with the exception of \(g_j'({\mathbf{x}}) = {\mathbf{x}}- \eta \nabla f({\mathbf{x}}; {\mathbf{d}}_{\pi_j^{(k)}}')\) for the index \(j\) such that \(\pi_j^{(k)} = t\). Let \({\mathbf{x}}_{n+1}^{(k)}\), \(({\mathbf{x}}_{n+1}^{(k)})'\) be the output of the CNI on dataset \({\mathsf{D}}\) and \({\mathsf{D}}'\), respectively.

By Assumption 3, \(f({\mathbf{x}}; {\mathbf{d}}_i)\) is \(G\)-Lipschitz, \(\forall i\in [n]\), and hence, \[\begin{align} \sup_{{\mathbf{w}}}\| g_j({\mathbf{x}}) - g_j'({\mathbf{x}}) \| = \sup_{{\mathbf{w}}}\| \eta \nabla f({\mathbf{x}}; {\mathbf{d}}_{t}) - \eta \nabla f({\mathbf{x}}; {\mathbf{d}}_{t}') \| \leq 2 \eta G \end{align}\]

We now apply Theorem 2 with \(a_1, \dots, a_{j-1} = 0\) and \(a_{j}, \dots, a_n = \frac{2\eta G}{n - j + 1}\). Note that \(s_{\pi_j^{(k)}} = 2 \eta G\) and \(s_{i} = 0\), \(\forall i \neq \pi_j^{(k)}\). In addition, \(z_i \geq 0\) for all \(i \leq n\) and \(z_n = 0\). Hence, \[\begin{align} D_{\alpha}\infdivx{{\mathbf{x}}_{n+1}^{(k)}}{({\mathbf{x}}_{n+1}^{(k)})'} \leq \sum_{i=j}^{n} \frac{\alpha}{2 \eta^2 \sigma^2} \cdot \frac{4 \eta^2 G^2}{(n - j + 1)^2} = \frac{2 \alpha G^2}{\sigma^2 (n-j + 1)} \end{align}\] The maximum privacy loss happens when \(j = n\), that is, when the sample \({\mathbf{d}}_{t}\) is the last one being processed in epoch \(k\). And it is not hard to see that \(\max_{j\in [n]} D_{\alpha}\infdivx{{\mathbf{x}}_{n+1}^{(k)}}{({\mathbf{x}}_{n+1}^{(k)})'} \leq \frac{2\alpha G^2}{\sigma^2}\), which implies \({\mathbf{x}}_{n+1}^{(k)}\) in Algorithm 1 is \((\alpha, \frac{2\alpha G^2}{\sigma^2})\)-RDP, for \(\alpha > 1\). The output of epoch \(k\), \({\mathbf{x}}_1^{(k+1)}\) can be seen as a post-processing step of \({\mathbf{x}}_{n+1}^{(k)}\), and hence, \({\mathbf{x}}_1^{(k+1)}\) is also \((\alpha, \frac{2\alpha G^2}{\sigma^2})\)-RDP.

By Proposition 3, the output \({\mathbf{x}}_1^{(K+1)}\) is \((\alpha, \frac{2\alpha G^2 K}{\sigma^2})\)-RDP. And by Proposition 2, \({\mathbf{x}}_1^{(K+1)}\) is \((\frac{2\alpha G^2 K}{\sigma^2} + \frac{\log 1/\delta}{\alpha - 1}, \delta)\)-DP, for \(\alpha > 1\) and \(\delta \in (0, 1)\). ◻

Proof of Lemma 18. The proof is similar to the proof of Lemma 16 showing the privacy loss of \(\textit{DP-ShuffleG}\). If the learning rate is set as \(\eta \leq 1/L^*\) for \(\textit{Priv-Pub-ShuffleG}\) and \(\textit{Pub-Priv-ShuffleG}\) and \(\eta \leq 1/\max\{L, L^{*}\}\) for \(\textit{Interleaved-ShuffleG}\), it is then guaranteed that each gradient step in one epoch is “contractive”, which enables us to apply PABI (Theorem 2) to reason about the per-epoch privacy loss.

The per-epoch privacy loss of \(\textit{Priv-Pub-ShuffleG}\) and \(\textit{Pub-Priv-ShuffleG}\) is the same as the per-epoch privacy loss in \(\textit{DP-ShuffleG}\) whenever the private dataset \({\mathsf{D}}\) is used during the epoch. Specifically, for \(\alpha > 1\),

• For \(\textit{Priv-Pub-ShuffleG}\), \({\mathbf{x}}_{1}^{(k+1)}\) is \((\alpha, \frac{2\alpha G^2}{(\sigma_{\text{prp}})^2})\)-RDP, if \(k \leq S\) and there is no privacy loss 0 otherwise.

• For \(\textit{Pub-Priv-ShuffleG}\), \({\mathbf{x}}_{1}^{(k+1)}\) is \((\alpha, \frac{2\alpha G^2}{(\sigma_{\text{pup}})^2})\)-RDP, if \(S+1 \leq k \leq K\), and there is no privacy loss 0 otherwise.

By applying composition (Proposition 3) across \(K\) and \(K-S\) epochs for \(\textit{Priv-Pub-ShuffleG}\) and \(\textit{Pub-Priv-ShuffleG}\), respectively, and subsequently converting the RDP bound to a DP bound using Proposition 2, we obtain the overall privacy loss as stated in the lemma statement.

For \(\textit{Interleaved-ShuffleG}\), we consider two neighboring datasets \({\mathsf{D}}= \{{\mathbf{d}}_1,\dots,{\mathbf{d}}_t,\dots, {\mathbf{d}}_n\}\) and \({\mathsf{D}}' = \{{\mathbf{d}}_1, \dots, {\mathbf{d}}_t', \dots, {\mathbf{d}}_n\}\) that differ at some index \(t \in [n]\). In every epoch, only the first \(n_d\) steps use samples from the private dataset \({\mathsf{D}}\), and the remaining steps all use public samples. Hence, \(t\) can only occur at step \(j \leq n_d\) in the sequence of updates in every epoch.

We apply Theorem 2 with \(a_1, \dots, a_{j-1} = 0\) and \(a_j,\dots, a_n = \frac{2\eta G^{*}}{n-j+1}\), where \(j \leq n_d\). Note that \(s_{\pi_j^{(k)}} = 2\eta G^{*}\) and \(s_i = 0\), \(\forall i\neq \pi_j^{(k)}\). In addition, \(z_i \geq 0\) for all \(i\leq n\) and \(z_n = 0\). Hence, \[\begin{align} D_{\alpha}\infdivx{{\mathbf{x}}_{n+1}^{(k)}}{({\mathbf{x}}_{n+1}^{(k)})'} \leq \sum_{i=j}^{n} \frac{\alpha}{2 \eta^2 (\sigma_{\text{int}})^2} \cdot \frac{4\eta^2 (G^{*})^2}{(n-j+1)^2} = \frac{2\alpha (G^{*})^2}{(\sigma_{\text{int}})^2(n-j+1)} \end{align}\] where \(({\mathbf{x}}_{n+1}^{(k)})'\) is the point obtained by optimizing on the neighboring dataset \({\mathsf{D}}'\).

Since \(j \leq n_d\), the maximum privacy loss happens at \(j = n_d\), that is, when the sample \({\mathbf{d}}_t\) is used at step \(n_d\) in one epoch. And so \[\begin{align} \max D_{\alpha}\infdivx{{\mathbf{x}}_{n+1}^{(k)}}{({\mathbf{x}}_{n+1}^{(k)})'} \leq \frac{2\alpha (G^{*})^2}{(\sigma_{\text{int}})^2 (n-n_d+1)} \end{align}\] which implies \({\mathbf{x}}_{n+1}^{(k)}\) and hence, \({\mathbf{x}}_{1}^{(k+1)}\), is \((\alpha, \frac{2\alpha (G^{*})^2}{(\sigma_{\text{int}})^2 (n-n_d+1)} )\)-RDP.

Applying composition (Proposition 3) across \(K\) epochs and converting the RDP bound to a DP bound using Proposition 2 leads to the overall privacy loss as stated in the lemma statement. ◻

Proof of Lemma 19. For epoch \(k\in [K]\), \[\begin{align} {\mathbf{x}}_{1}^{(k+1)} = \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in\mathbb{R}^{d}} n \lambda \|{\mathbf{x}}\|_1 + \frac{\|{\mathbf{x}}- {\mathbf{x}}_{n+1}^{(k)}\|^2}{2\eta} \end{align}\] and for \(j\in [d]\), \[\begin{align} {\mathbf{x}}_{1, j}^{(k+1)} = \begin{cases} {\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n & \text{if {\mathbf{x}}_{n+1, j}^{(k)} > \eta \lambda n}\\ {\mathbf{x}}_{n+1, j}^{(k)} + \eta \lambda n & \text{if {\mathbf{x}}_{n+1, j}^{(k)} < -\eta \lambda n}\\ 0 & \text{if |{\mathbf{x}}_{n+1, j}^{(k)}| \leq \eta \lambda n} \end{cases} := g({\mathbf{x}}_{n+1,j}^{(k)}) \end{align}\] where \({\mathbf{x}}_{n+1,j}^{(k)}\) and \({\mathbf{x}}_{1,j}^{(k+1)}\) denote the \(j\)-th coordinate of \({\mathbf{x}}_{n+1}^{(k)}\) and \({\mathbf{x}}_{1}^{(k+1)}\), respectively.

For \(i\in [n]\), conditional on \(\rho_k^{(k)}, \forall k\neq i\), \[\begin{align} \label{eq:l195reg95cond95exp} \mathbb{E}_{\rho_i^{(k)}}\left[\left\langle {\mathbf{x}}_{1}^{(k+1)}, \rho_i^{(k)} \right\rangle \mid \{\rho_k^{(k)}\}_{k\neq i}\right] = \sum_{j=1}^{d} \mathbb{E}_{\rho_{i,j}^{(k)}}\left[ {\mathbf{x}}_{1, j}^{(k+1)} \rho_{i, j}^{(k)} \mid \{\rho_{l, j}^{(k)}\}_{l \neq i}\right] \end{align}\tag{50}\] where \(\rho_{i, j}^{(k)} \in {\mathcal{N}}(0, (\sigma^{(k)})^2)\) denotes the \(j\)-th coordinate of the noise vector \(\rho_i^{(k)}\), \(\forall i\in [n], j\in[d]\).

For \(i\in [n]\) and \(j\in [d]\), let \(m_{i,j}^{(k)}\) denote the value of the random variable \(\rho_{i, j}^{(k)}\). \[\begin{align} &\mathbb{E}_{\rho_{i,j}^{(k)}}\left[{\mathbf{x}}_{1,j}^{(k+1)} \rho_{i, j}^{(k)} \mid \{\rho_{k, j}^{(k)}\}_{k \neq i} \right] = \mathbb{E}_{\rho_{i,j}^{(k)}}\left[ g({\mathbf{x}}_{n+1,j}^{(k)}) \rho_{i, j}^{(k)} \mid \{\rho_{l, j}\}_{l \neq i}^{(k)} \right]\\ &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \Bigg( \int_{{\mathbf{x}}_{n+1,j}^{(k)} < -\eta \lambda n} \underbrace{({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n)}_{:=u_1} \underbrace{ m_{i, j}^{(k)} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} }_{:=d v_1} dm_{i, j}^{(k)}\\ \nonumber &\quad + \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} \underbrace{({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n)}_{:= u_2} \underbrace{m_{i, j}^{(k)} e^{-\frac{(m_{i, j}^{(k)})^2}{2 (\sigma^{(k)})^2}}}_{:=d v_2} dm_{i, j}^{(k)} \Bigg) \end{align}\]

Let \(u_1 = {\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n\) and \(d v_1 = m_{i,j}^{(k)} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} dm_{i, j}^{(k)}\). Then, \(d u_1 = \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} d m_{i,j}^{(k)}\) and \(v_1 = -(\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}\). Similarly, let \(u_2 = {\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n\) and \(d v_2 = m_{i,j}^{(k)} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}\). Then, \(d u_2 = \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}}\) and \(v_2 = -(\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}\). Using integration by parts, \[\begin{align} \nonumber &\frac{1}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1, j}^{(k)} < -\eta \lambda n} ({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) m_{i,j}^{(k)} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} d m_{i,j}^{(k)}\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \Big[ - ({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} \Big]_{{\mathbf{x}}_{n+1,j}^{(k)} < -\eta \lambda n}\\ \nonumber &\quad - \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1, j}^{(k)} < -\eta \lambda n} - (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)} )^2}{2 (\sigma^{(k)})^2}} \frac{\partial {\mathbf{x}}_{n+1, j}^{(k)}}{\partial \rho_{i, j}} dm_{i,j}^{(k)}\\ \label{eq:appendix95l1951} &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \Big[ - ({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} \Big]_{{\mathbf{x}}_{n+1,j}^{(k)} < -\eta \lambda n}\\ \nonumber &\quad + \frac{ (\sigma^{(k)})^2}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1, j}^{(k)} < - \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} dm_{i,j}^{(k)} \end{align}\tag{51}\] and \[\begin{align} \nonumber &\frac{1}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} ({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n) m_{i,j}^{(k)} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} d m_{i,j}^{(k)}\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}}\left[ - ({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n}\\ \nonumber &\quad - \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} - (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}} dm_{i,j}^{(k)}\\ \label{eq:appendix95l1952} &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}}\left[ - ({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n}\\ \nonumber &\quad + \frac{(\sigma^{(k)})^2}{\sigma^{(k)} \sqrt{2\pi}} \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} d m_{i,j}^{(k)} \end{align}\tag{52}\]

Summing up Eq. 51 and Eq. 52 , \[\begin{align} \label{eq:l195reg95exp95single95coord} &\mathbb{E}_{\rho_{i,j}^{(k)}}\left[ {\mathbf{x}}_{1,j}^{(k+1)} \rho_{i, j}^{(k)} \mid \{\rho_{k,j}^{(k)}\}_{k\neq i} \right]\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \Bigg( \Big[ -({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \Big]_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n} + \Big[ -({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \Big]_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n}\Bigg) \\ \nonumber &\quad + \frac{ (\sigma^{(k)})^2}{ (\sigma^{(k)}) \sqrt{2\pi}} \Bigg( \int_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} } e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}dm_{i,j}^{(k)} + \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} } e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} dm_{i,j}^{(k)} \Bigg) \end{align}\tag{53}\]

We use \({\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)})\) to denote the value of \({\mathbf{x}}_{n+1,j}^{(k)}\) as a function of the noise value \(m_{i,j}^{(k)}\).

By Eq. 37 , \(\left\| \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} \leq n \eta^2 \widehat{L}^{(k)*}\) is bounded, \(\forall i\in [n], k\in [K]\), and hence, \(|\frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)})}{\partial m_{i,j}^{(k)}}|\) is also bounded. This implies that \(\frac{1}{\sqrt{2\pi}} \cdot -({\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}\rightarrow 0\) and \(\frac{1}{\sqrt{2\pi}}\cdot -({\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} \rightarrow 0\) as \(m_{i,j}^{(k)} \rightarrow \infty\) or \(m_{i,j}^{(k)} \rightarrow -\infty\).

We now compute the terms in the above Eq. 53 separately. \[\begin{align} &\frac{1}{\sigma^{(k)} \sqrt{2\pi}}\left[ -({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n}\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}}\left[ -({\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{\inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < - \eta \lambda n\}}^{\sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < - \eta \lambda n\}} \end{align}\]

Note that \(\sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < - \eta \lambda n\}\) is finite and \(\inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < - \eta \lambda n\} \rightarrow -\infty\). Let \(m_{+} = \sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < - \eta \lambda n\}\), and the above is then \[\begin{align} \nonumber &\frac{1}{\sigma^{(k)} \sqrt{2\pi}}\left[ -({\mathbf{x}}_{n+1,j}^{(k)} + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n}\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}}\cdot -({\mathbf{x}}_{n+1,j}^{(k)}(m_{+}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{m_{+}^2}{2 (\sigma^{(k)})^2}} - 0\\ \label{eq:l195reg95t1} &= -\frac{1}{\sigma^{(k)} \sqrt{2\pi}}({\mathbf{x}}_{n+1,j}^{(k)}(m_{+}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{m_{+}^2}{2 (\sigma^{(k)})^2}} \end{align}\tag{54}\]

Similarly, note that \(\sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\}\rightarrow \infty\) and \(\inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\}\) is finite. Let \(m_{-} = \inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\}\). \[\begin{align} \nonumber &\frac{1}{(\sigma^{(k)}) \sqrt{2\pi}} \left[ -({\mathbf{x}}_{n+1,j}^{(k)} - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n}\\ \nonumber &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} \left[ -({\mathbf{x}}_{n+1,j}^{(k)}(m_{i,j}^{(k)}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} \right]_{\inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\}}^{\sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\} }\\ \nonumber &= 0 - \frac{1}{\sigma^{(k)} \sqrt{2\pi}}\cdot -({\mathbf{x}}_{n+1,j}^{(k)}(m_{-}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{-})^2}{2 (\sigma^{(k)})^2}}\\ \label{eq:l195reg95t2} &= \frac{1}{\sigma^{(k)} \sqrt{2\pi}} ({\mathbf{x}}_{n+1,j}^{(k)}(m_{-}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{-})^{2}}{2 (\sigma^{(k)})^2}} \end{align}\tag{55}\]

Furthermore, \[\begin{align} \nonumber &\frac{(\sigma^{(k)})^2}{\sigma^{(k)} \sqrt{2\pi}}\left( \int_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} } e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}}dm_{i,j}^{(k)} + \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} } e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} dm_{i,j}^{(k)} \right)\\ \nonumber &\leq \frac{(\sigma^{(k)})^2}{\sigma^{(k)} \sqrt{2\pi}}\left( \int_{{\mathbf{x}}_{n+1,j}^{(k)} < - \eta \lambda n} \left|\frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} }\right| e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}}dm_{i,j}^{(k)} + \int_{{\mathbf{x}}_{n+1,j}^{(k)} > \eta \lambda n} \left|\frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}} \right| e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} dm_{i,j}^{(k)} \right)\\ \nonumber &\leq \frac{(\sigma^{(k)})^2}{\sigma^{(k)} \sqrt{2\pi}} \int_{\mathbb{R}} \left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i,j}^{(k)}} \right| e^{-\frac{(m_{i,j}^{(k)})^2}{2 (\sigma^{(k)})^2}} d m_{i,j}^{(k)}\\ \nonumber &\leq (\sigma^{(k)})^2 \max\left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} \right|\cdot \frac{1}{\sigma^{(k)}\sqrt{2\pi}} \int_{\mathbb{R}} e^{-\frac{(m_{i,j}^{(k)})^2}{2(\sigma^{(k)})^2}} d m_{i,j}^{(k)}\\ \label{eq:l195reg95t3} &= (\sigma^{(k)})^2 \max\left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} \right| \end{align}\tag{56}\]

Plugging Eq. 54 , Eq. 55 and Eq. 56 back to Eq. 53 , \[\begin{align} &\mathbb{E}_{\rho_{i,j}^{(k)}}\left[{\mathbf{x}}_{1,j}^{(k+1)} \rho_{i, j}^{(k)} \mid \{\rho_{k, j}^{(k)}\}_{k \neq i} \right] \leq (\sigma^{(k)})^2 \max\left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)} } \right|\\ \nonumber &\quad \underbrace{-\frac{1}{\sigma^{(k)}\sqrt{2\pi}}({\mathbf{x}}_{n+1,j}^{(k)}(m_{+}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{m_{+}^2}{2(\sigma^{(k)})^2}} + \frac{1}{\sigma^{(k)} \sqrt{2\pi}} ({\mathbf{x}}_{n+1,j}^{(k)}(m_{-}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{-})^{2}}{2 (\sigma^{(k)})^2}} }_{:= \Delta_{i,j}^{(k)}} \end{align}\]

where \(m_{+} = \sup\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) < -\eta \lambda n\}\) and \(m_{-} = \inf\{m: {\mathbf{x}}_{n+1,j}^{(k)}(m) > \eta \lambda n\}\). We note that \(-({\mathbf{x}}_{n+1,j}^{(k)}(m_{+}) + \eta \lambda n) \geq 0\) and \(({\mathbf{x}}_{n+1,j^{(k)}}(m_{-}) - \eta \lambda n) \geq 0\).

Let \(\Delta_{i, j}^{(k)} = -\frac{1}{\sigma^{(k)} \sqrt{2\pi}}({\mathbf{x}}_{n+1,j}^{(k)}(m_{+}) + \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{m_{+}^2}{2 (\sigma^{(k)})^2}} + \frac{1}{\sigma^{(k)} \sqrt{2\pi}} ({\mathbf{x}}_{n+1,j}^{(k)}(m_{-}) - \eta \lambda n) (\sigma^{(k)})^2 e^{-\frac{(m_{-})^{2}}{2 (\sigma^{(k)})^2}}\). Note that the subscript \(i\) here indicates in \(\Delta_{i, j}^{(k)}\), the value \({\mathbf{x}}_{n+1,j}^{(k)}(m)\) is a deterministic function of the noise \(\rho_{i}^{(k)}\)’s value \(m\), by fixing the values of \(\{\rho_{k}^{(k)}\}\), \(\forall i\neq k\). Also, when \(\eta \lambda n = 0\), we can integrate over \(\mathbb{R}\) and in this case \(\Delta_j^{(k)} = 0\). This case is essentially what Stein’s lemma addresses.

Following Eq. 50 , for \(i\in [n]\), conditional on \(\rho_k^{(k)}, \forall k\neq i\), \[\begin{align} \mathbb{E}_{\rho_i^{(k)}}\left[\left\langle {\mathbf{x}}_{1}^{(k+1)}, \rho_i^{(k)} \right\rangle \mid \{\rho_k^{(k)}\}_{k\neq i}\right] &= \sum_{j=1}^{d} \mathbb{E}_{\rho_{i,j}^{(k)}}\left[ {\mathbf{x}}_{1, j}^{(k+1)} \rho_{i, j}^{(k)} \mid \{\rho_{k, j}^{(k)}\}_{k \neq i}\right]\\ &\leq (\sigma^{(k)})^2 \sum_{j=1}^{d} \max\left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} \right| + \sum_{j=1}^{d} \mathbb{E}\left[\Delta_{i,j}^{(k)} \mid \{\rho_k^{(k)}\}_{k\neq i} \right] \end{align}\]

Note that \(\sum_{j=1}^{d} \max \left| \frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}} \right| = \sum_{j=1}^{d} \max \left| \left[\frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_{i}^{(k)}}\right]_{j,j} \right|\), i.e., sum of the absolute value of the \(j\)-th diagonal entry of the Jacobian matrix \(\frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}}\). Again, by Eq. 37 , \(\left\| \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} \leq n \eta^2 \widehat{L}^{(k)*}\) is bounded, \(\forall i\in [n], k\in [K]\). Therefore, for \(i\in [n]\), \[\begin{align} \sum_{j=1}^{d}\max\left|\frac{\partial {\mathbf{x}}_{n+1,j}^{(k)}}{\partial \rho_{i, j}^{(k)}}\right| \leq \max \left\| \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_{i}^{(k)}} \right\|_{tr} \leq d \cdot \max \left\| \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_{i}^{(k)}} \right\|_{op} \leq d n \eta^2 \widehat{L}^{(k)*} \end{align}\] where \(\|\cdot\|\) denotes the trace norm of a matrix. Hence, by law of total expectation, \[\begin{align} \mathbb{E}_{\rho_{i}^{(k)}}\left[ \left\langle {\mathbf{x}}_1^{(k+1)}, \rho_i^{(k)} \right\rangle \right] &= \mathbb{E}\left[\mathbb{E}_{\rho_i^{(k)}}\left[\left\langle {\mathbf{x}}_{1}^{(k+1)}, \rho_i^{(k)} \right\rangle \mid \{\rho_k^{(k)}\}_{k\neq i}\right]\right]\\ &\leq (\sigma^{(k)})^2 d n \eta^2 \widehat{L}^{(k)*} + \sum_{j=1}^{d}\mathbb{E}\left[\mathbb{E}_{\rho_i^{(k)}}\left[ \Delta_{i,j}^{(k)} \mid \{\rho_{k}^{(k)}\}_{k\neq i}\right]\right]\\ &\leq (\sigma^{(k)})^2 d n \eta^2 \widehat{L}^{(k)*} + \sum_{j=1}^{d} \frac{2 (\sigma^{(k)})^2}{\sqrt{2\pi}} B = (\sigma^{(k)})^2 d n \eta^2 \widehat{L}^{(k)*} + \frac{2 d (\sigma^{(k)})^2 }{\sqrt{2\pi}} B \end{align}\] where the last inequality is by Assumption 9 and the fact that \(\frac{1}{(\sigma^{(k)})\sqrt{2\pi}} e^{-\frac{m^2}{2(\sigma^{(k)})^2}}\leq 1\). Therefore, \[\begin{align} \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n} \langle \rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} + \frac{2 d (\sigma^{(k)})^2}{\sqrt{2\pi}} B \end{align}\] ◻

Proof of Lemma 20. For epoch \(k\in [K]\), \[\begin{align} {\mathbf{x}}_1^{(k+1)} = \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in \mathbb{R}^{d}} n {\mathcal{I}}\{{\mathbf{x}}\in {\mathsf{B}}\} + \frac{\|{\mathbf{x}}- {\mathbf{x}}_{n+1}^{(k)}\|^2}{2 \eta} = \mathop{\mathrm{arg\,min}}_{{\mathbf{x}}\in {\mathsf{B}}} \|{\mathbf{x}}- {\mathbf{x}}_{n+1}^{(k)}\| \end{align}\] \({\mathbf{x}}_{1}^{(k+1)}\) is essentially the projection of \({\mathbf{x}}_{n+1}^{(k)}\) onto \({\mathsf{B}}\).

For \(i\in [n]\), \[\begin{align} \mathbb{E}\left[\left\langle {\mathbf{x}}_{1}^{(k+1)}, \rho_i^{(k)} \right\rangle \right] &= \mathbb{E}\left[\left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle\right] + \mathbb{E}\left[\left\langle {\mathbf{x}}_{1}^{(k+1)} - {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle\right]\\ &\leq \mathbb{E}\left[\left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle\right] + \frac{1}{2}\mathbb{E}\left[\left\| \rho_i^{(k)}\right\|^2\right] + \frac{1}{2}\mathbb{E}\left[\left\| {\mathbf{x}}_{n+1}^{(k)} - {\mathbf{x}}_{1}^{(k)}\right\|^2 \right] \end{align}\] where the last step is by Young’s inequality.

We apply Stein’s lemma to bound \(\mathbb{E}\left[\left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle\right]\) as follows: Conditional on \(\rho_{j}^{(k)}, \forall j\neq i\), \[\begin{align} \mathbb{E}_{\rho_i^{(k)}}\left[\left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle \mid \{\rho_j^{(k)}\}_{j\neq i}\right] = (\sigma^{(k)})^2\cdot \mathbb{E}_{\rho_i^{(k)}}\left[\text{tr}\left( \frac{\partial {\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}}\right) \mid \{\rho_j^{(k)}\}_{j\neq i}\right] \end{align}\]

By Eq. 37 , if \(\eta \leq \frac{1}{\widehat{L}^{(k)*}}\), \(\forall i \in [n]\) and \(s\in [K]\), \(\left\| \frac{{\mathbf{x}}_{n+1}^{(k)}}{\partial \rho_i^{(k)}} \right\|_{op} \leq n \eta^2 \widehat{L}^{(k)*}\). And so for \(i\in [n]\), \[\begin{align} \label{eq:noise95bias95reg95proj95t1} \mathbb{E}\left[\left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)}\right\rangle\right] = \mathbb{E}\left[\mathbb{E}_{\rho_i^{(k)}}\left[ \left\langle {\mathbf{x}}_{n+1}^{(k)}, \rho_i^{(k)} \right\rangle \mid \{\rho_j^{(k)}\}_{j\neq i}\right]\right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} \end{align}\tag{57}\]

By Lemma 13, \[\begin{align} \label{eq:noise95bias95reg95proj95t2} \mathbb{E}\left[\left\|\rho_i^{(k)} \right\|^2\right] \leq d (\sigma^{(k)})^2 \end{align}\tag{58}\]

We use similar techniques to bound \(\mathbb{E}\left[\left\| {\mathbf{x}}_{n+1}^{(k)} - {\mathbf{x}}_1^{(k)} \right\|^2\right]\) as in the convergence proof in section 11.2 and in Lemma 14. Specifically, based on the update in Algorithm 1,

\[\begin{align} \nonumber &\mathbb{E}\left[ \left\| {\mathbf{x}}_{n+1}^{(k)} - {\mathbf{x}}_1^{(k)}\right\|^2 \right]\\ \nonumber &= \eta^2 \mathbb{E}\Big[\Big\| \sum_{j=1}^{n_d^{(k)}} \Big(\nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \rho_j^{(k)} \Big) + \sum_{j=n_d^{(k)}+1}^{n} (\nabla f_{j-n_d^{(k)}}^{(k, pub)}\Big({\mathbf{x}}_{j}^{(k)}) + \rho_j^{(k)} \Big) \Big\|^2 \Big]\\ \nonumber &\leq 5\eta^2 \Bigg( \mathbb{E}\left[\Big\|\sum_{j=1}^{n_d^{(k)}} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) + \sum_{j=n_d^{(k)}+1}^{n} \nabla f_{j-n_d^{(k)} }^{(k, pub)}({\mathbf{x}}_j^{(k)}) - \sum_{j=1}^{n_d^{(k)} }\nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{n} \nabla f_{j-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \Big\|^2\right]\\ \nonumber &\quad + \mathbb{E}\left[ \Big\| \sum_{j=n_d^{(k)}+1}^{n} \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}}) - \sum_{j=n_d^{(k)}+1}^{n}\nabla f_{\pi_j^{(k)}}({\mathbf{z}}) \Big\|^2 \right]\\ \nonumber &\quad + \mathbb{E}\left[\Big\| \sum_{j=1}^{n} \nabla f_{\pi_j^{(k)}}({\mathbf{z}}) - \sum_{j=1}^{n} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2\right] + \mathbb{E}\left[\Big\| \sum_{j=1}^{n} \nabla f_{\pi_j^{(k)}}({\mathbf{x}}^*) \Big\|^2\right] + \mathbb{E}\left[\Big\| \sum_{j=1}^{n} \rho_j^{(k)} \Big\|^2 \right] \Bigg)\\ \label{eq:noise95bias95reg95proj95t3} &\leq 5\eta^2 \Bigg( n\sum_{j=1}^{n_d^{(k)}} \mathbb{E}\left[\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2\right] + n \sum_{j=n_d^{(k)}+1}^{n} \mathbb{E}\left[\Big\| \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}}) \Big\|^2 \right]\\ \nonumber &\quad + (C_n^{(k)})^2 + n L \mathbb{E}[ B_F({\mathbf{z}}, {\mathbf{x}}^*) ] + n^2 \sigma_{any}^2 + n d (\sigma^{(k)})^2 \Bigg) \end{align}\tag{59}\] where the last inequality is due to Jensen’s inequality, Assumption 6, Lemma 6, the definition of \(\sigma_{any}^2\) and Lemma 13.

Combining Eqs. 57 , 58 , and 59 , and noting that \({\mathbf{z}}\) is independent of \(\rho_i^{(k)}\) for all \(i \in [n]\), we obtain the inequality (?? ) stated in the lemma statement. ◻

Proof of Lemma 21. Following Lemma 9, 10 and 11, after taking expectation, there is for any \({\mathbf{z}}\in \mathbb{R}^{d}\), and for \(k\in [K]\), \[\begin{align} \label{eq:proj95interm} &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}})\right] \leq \mathbb{E}\left[ H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}})\right] + \frac{\mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2 \right]}{2n \eta}\\ \nonumber &\quad - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2\right] - \frac{1}{2n \eta}\mathbb{E}\left[\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \right]\\ \nonumber &\quad + \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\langle -\rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle\right] + \widehat{L}^{(k)}\mathbb{E}\left[\| {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\right] + 5\eta^2 \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1} \widehat{L}^{(k)*} (C_i^{(k)})^2\\ \nonumber &\quad + 10 \eta^2 n^2 \widehat{L}^{(k)} L \mathbb{E}\left[B_F({\mathbf{z}}, {\mathbf{x}}^*)\right] + 5\eta^2 n^2 \widehat{L}^{(k)} \sigma_{any}^2 + 5\eta^2 nd (\sigma^{(k)})^2 \widehat{L}^{(k)}\\ \nonumber &\quad + 5\eta^2 n \widehat{L}^{(k)} \sum_{j=1}^{n_d^{(k)}} \mathbb{E}\left[\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_{j}^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2\right] + 5\eta^2 n \widehat{L}^{(k)} \sum_{j=n_d^{(k)}+1}^{n} \mathbb{E}\left[\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)} - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}})\Big\|^2\right]\\ \nonumber &\quad - \frac{1}{n} \Big( \sum_{i=1}^{n_d^{(k)}} \frac{ \mathbb{E}\left[\left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2 \right] }{2 L_{\pi_i^{(k)}}} + \sum_{i=n_d^{(k)}+1}^{n} \frac{ \mathbb{E}\left[ \left\| \nabla f_{i-n_d}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d}^{(k, pub)}({\mathbf{z}}) \right\|^2\right] }{2\widetilde{L}_{i-n_d}^{(k)}} \Big) \end{align}\tag{60}\]

By Lemma 20, \[\begin{align} \label{eq:noise95bias95proj95op} &\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n} \langle -\rho_i^{(k)}, {\mathbf{x}}_1^{(k+1)} - {\mathbf{z}}\rangle \right] \leq (\sigma^{(k)})^2 nd \eta^2 \widehat{L}^{(k)*} + \frac{1}{2}d (\sigma^{(k)})^2\\ \nonumber &\quad + \frac{5\eta^2}{2} \Bigg( n\sum_{j=1}^{n_d^{(k)}} \mathbb{E}\left[\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_j^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2\right] + n \sum_{j=n_d^{(k)}+1}^{n} \mathbb{E}\left[\Big\| \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{x}}_j^{(k)}) - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}}) \Big\|^2 \right] \\ \nonumber &\quad + (C_n^{(k)})^2 + n L \mathbb{E}[B_F({\mathbf{z}}, {\mathbf{x}}^*) ] + n^2 \sigma_{any}^2 + n d (\sigma^{(k)})^2 \Bigg) \end{align}\tag{61}\]

Plugging Eq. 61 back to Eq. 60 , \[\begin{align} \nonumber &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}})\right] \leq \mathbb{E}\left[ H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}})\right] + \frac{\mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2 \right]}{2n \eta}\\ \nonumber &\quad - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2\right] - \frac{1}{2n \eta}\mathbb{E}\left[\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \right]\\ \nonumber &\quad + \widehat{L}^{(k)}\mathbb{E}\left[\| {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\right] + 5\eta^2 \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1} \widehat{L}^{(k)*} (C_i^{(k)})^2 + \frac{5}{2}\eta^2 (C_n^{(k)})^2\\ \nonumber &\quad + 10 \eta^2 n^2 L (\widehat{L}^{(k)}+1) \mathbb{E}\left[B_F({\mathbf{z}}, {\mathbf{x}}^*)\right] + 5\eta^2 n^2 (\widehat{L}^{(k)} +1) \sigma_{any}^2 + 6 \eta^2 nd (\sigma^{(k)})^2 (\widehat{L}^{(k)*}+1) + \frac{1}{2}d (\sigma^{(k)})^2 \\ \nonumber &\quad + 5\eta^2 n (\widehat{L}^{(k)} +1 ) \sum_{j=1}^{n_d^{(k)}} \mathbb{E}\left[\Big\| \nabla f_{\pi_j^{(k)}}({\mathbf{x}}_{j}^{(k)}) - \nabla f_{\pi_j^{(k)}}({\mathbf{z}})\Big\|^2\right]\\ \nonumber &\quad + 5\eta^2 n (\widehat{L}^{(k)} + 1 )\sum_{j=n_d^{(k)}+1}^{n} \mathbb{E}\left[\Big\| \nabla f_{j-n_d^{(k)}}^{(k, pub)} - \nabla f_{j-n_d^{(k)}}^{(k,pub)}({\mathbf{z}})\Big\|^2\right]\\ \nonumber &\quad - \frac{1}{n} \Big( \sum_{i=1}^{n_d^{(k)}} \frac{ \mathbb{E}\left[\left\|\nabla f_{\pi_i^{(k)}}({\mathbf{x}}_i) - \nabla f_{\pi_i^{(k)}}({\mathbf{z}}) \right\|^2 \right]}{2 L_{\pi_i^{(k)}}} + \sum_{i=n_d^{(k)}+1}^{n} \frac{ \mathbb{E}\left[\left\| \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{x}}_i^{(k)}) - \nabla f_{i-n_d^{(k)}}^{(k, pub)}({\mathbf{z}}) \right\|^2 \right]}{2\widetilde{L}_{i-n_d^{(k)}}^{(k)}} \Big) \end{align}\]

If one sets the learning rate \(\eta\) such that \[\begin{align} 5\eta^2 n(\widehat{L}^{(k)} + 1) \leq \frac{1}{n}\cdot \frac{1}{2\widehat{L}^{(k)*}}, \quad \Rightarrow \eta \leq \frac{1}{n \sqrt{10 (\widehat{L}^{(k)} + 1) \widehat{L}^{(k)*}}} \end{align}\] then it follows that \[\begin{align} \nonumber &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}})\right] \leq \mathbb{E}\left[ H^{(k)}({\mathbf{x}}_1^{(k+1)}) - H^{(k)}({\mathbf{z}})\right] + \frac{\mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2 \right]}{2n \eta}\\ \nonumber &\quad - (\frac{1}{2n \eta} + \frac{\mu_\psi}{2}) \mathbb{E}\left[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2\right] - \frac{1}{2n \eta}\mathbb{E}\left[\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2 \right]\\ \nonumber &\quad + \widehat{L}^{(k)}\mathbb{E}\left[\| {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2\right] + 5\eta^2 \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1} \widehat{L}^{(k)*} (C_i^{(k)})^2 + \frac{5}{2}\eta^2 (C_n^{(k)})^2\\ \nonumber &\quad + 10 \eta^2 n^2 L (\widehat{L}^{(k)}+1) \mathbb{E}\left[B_F({\mathbf{z}}, {\mathbf{x}}^*)\right] + 5\eta^2 n^2 (\widehat{L}^{(k)} +1) \sigma_{any}^2 + 6 \eta^2 nd (\sigma^{(k)})^2 (\widehat{L}^{(k)*}+1) + \frac{1}{2}d (\sigma^{(k)})^2 \end{align}\]

Finally, by Eq. 28 ,

\[\begin{align} \mathbb{E}\left[H^{(k)}({\mathbf{x}}_{1}^{(k+1)})\right] - \mathbb{E}\left[H^{(k)}({\mathbf{z}})\right] &\leq \frac{L_H^{(k)} + \beta}{2} \mathbb{E}\left[\|{\mathbf{x}}_{1}^{(k+1)} - {\mathbf{z}}\|^2\right] + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 \end{align}\] and hence, \[\begin{align} \nonumber &\mathbb{E}\left[G({\mathbf{x}}_1^{(k+1)}) - G({\mathbf{z}})\right] \leq \frac{1}{2n\eta}\Big(\mathbb{E}[\|{\mathbf{z}}- {\mathbf{x}}_1^{(k)}\|^2 ] - \mathbb{E}[\| {\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 ] \Big) + ( \frac{L_H^{(k)} + \beta}{2} - \frac{\mu_{\psi}}{2} ) \mathbb{E}[\| {\mathbf{z}}- {\mathbf{x}}_1^{(k+1)}\|^2 ] \\ \nonumber &\quad + (\widehat{L}^{(k)} - \frac{1}{2n \eta} ) \mathbb{E}[\| {\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)}\|^2] + \frac{1}{2n^2 \beta}(C_n^{(k)})^2 + 5\eta^2 \frac{1}{n}\sum_{i=n_d^{(k)}+1}^{n-1} \widehat{L}^{(k)*} (C_i^{(k)})^2 + \frac{5}{2}\eta^2 (C_n^{(k)})^2\\ \nonumber &\quad + 10 \eta^2 n^2 L (\widehat{L}^{(k)} +1) \mathbb{E}\left[B_F({\mathbf{z}}, {\mathbf{x}}^*)\right] + 5\eta^2 n^2 (\widehat{L}^{(k)} +1) \sigma_{any}^2 + 6 \eta^2 nd (\sigma^{(k)})^2 (\widehat{L}^{(k)*}+1) + \frac{1}{2}d (\sigma^{(k)})^2 \end{align}\]

Since \(\eta \leq \frac{1}{n\sqrt{10 (\widehat{L}^{(k)} + 1)\widehat{L}^{(k)*}}}\), it follows that \(\widehat{L}^{(k)} \leq \sqrt{(\widehat{L}^{(k)} + 1) \widehat{L}^{(k)*}} \leq \frac{1}{n \eta \sqrt{10}} \leq \frac{1}{2n\eta}\). Therefore, the term \((\widehat{L}^{(k)} - \frac{1}{2n \eta}) \mathbb{E}[\|{\mathbf{x}}_1^{(k+1)} - {\mathbf{x}}_1^{(k)} \|^2] \leq 0\), which then yields the inequality in the lemma statement. ◻