LOCKS: User Differentially Private and Federated Optimal Client Sampling

Stochastic Gradient Descent (SGD) functions by randomly selecting a subset of data points per round and computing their gradients. The update step in SGD uses the average gradient to modify the weights from the previous round. Optimal model weights can improve the trained model and its inference capabilities on unseen data. For high-dimensional non-convex parameter paces, obtaining optimal models is non-trivial and computationally heavy. Thus, improving the quality of gradients and accelerating the training process are fundamental goals for improving gradient algorithms.

However, as we often see in practice, the information assimilated in each gradient can vary widely. After the first few training epochs, the gradients of specific data points lose their value. (Katharopoulos and Fleuret, 2018). We could select data points randomly or by batching the entire training set per round. Both methods are inefficient and do not consider the information contributed by the gradients or the data points.

A way to assess the importance of each data point could be based on the magnitude of the gradient or loss value contributed by the data point (Loshchilov and Hutter, 2015), (Alain et al., 2015). Gradient magnitude refers to metrics like the $L_{1}$-norm or $L_{2}$-norm computed on individual gradients. Larger magnitudes suggest higher levels of information in gradients. For high-dimensional parameter models, gradient norms can be costly to compute. Computing loss values is straightforward but needs to reflect the gradient update accurately. In this work, we, therefore, focus on the magnitude of the gradient update. Such methods are based on Importance Sampling (IS) algorithms.

The rationale behind randomly picking data points per round is to obtain an unbiased estimate of the actual gradient. However, this unbiasedness comes at the cost of higher gradient variance. In such cases, Stochastic Variance Reduction Gradient (SVRG) techniques have been suggested to reduce the variance of the gradient.

Besides the gradient magnitude, we should prioritize diverse gradients. If two gradients are similar in the form of some similarity metric (ex., cosine similarity), then we may only need to use such a gradient. Gradient diversity should therefore be another basis for client selection.

This work further focuses on distributed and private machine-learning settings. Big data technologies have enabled massive leaps in predictive learning. However, these techniques commonly access private personal client data that can potentially cause severe harm to the owner if leaked. Such leaks are preventable under Federated Learning (FL) and Differential Privacy (DP), allowing owners tighter ownership over their data. For vanilla SGD, there are already techniques like FedAvg (Konečnỳ et al., 2016) and DP-SGD (Abadi et al., 2016) that can partially or fully protect private data. However, these algorithms’ privacy and convergence analysis cannot be directly applied to the algorithms proposed in this work.

In this work, we study the problem of partial client availability under Federated Learning under differential privacy. We analyze the expected gradient variance due to uniform sampling and the noise added by DP with adaptive server learning rates. As per our knowledge, such an exact theoretical analysis does not exist. Therefore, we provide analytical results and convergence guarantees in Theorem 5.1 in terms of the required iteration. We also suggested a modified approach that allows for lower communication rounds by simple scaling. We provide a pseudo-code for the algorithm suggested. We motivate the identification of other frameworks due to significant drawbacks to the one suggested in the reference papers.

Federated Learning involves training machine learning models on individual clients rather than sending the entire dataset to a central server. Clients process and train their datasets with an SGD variant on-device. At each round, the server selects a subset of its client for training. Clients only send their computed gradient to the server. The server computes the average gradient over these client gradients and updates the model. After each round, the server sends back the updated model. These rounds are repeated until the model converges, similar to vanilla training. With more rounds, the communication cost incurred by the clients and the server substantially increases. Also, with limited computational resources and data, the clients must train longer and for more rounds. Therefore, we prefer to lower the number of training rounds.

Differential Privacy (DP) is a mathematical framework over queries to a dataset that limits the leakage of a single client or data point in a dataset. However, even though we wish to learn aggregated values, the query outputs can disclose information about a particular individual in the dataset. Combining auxiliary public data with aggregated histograms or anonymized datasets can help us extract exact individual identities (Narayanan and Shmatikov, 2006). DP adds noise or performs specific sampling to limit the impact of a single client or data point on the query outputs, thus protecting individual privacy. When accessing data over multiple rounds, DP needs to add noise at each stage; thus, the DP cost is proportional to the number of rounds. Higher DP costs lead to practically trivial privacy for real-world applications. Thus, reducing the number of rounds is crucial to ensuring high privacy standards.

Therefore, an accelerated SGD algorithm will improve training quality and speeds and potentially lead to more private methods. Federated IS (FedIS) and Differentially Private IS (DPIS) leverage gradient magnitude and diversity to achieve this acceleration. We study approaches that combine some of these ideas and introduce new ones for private training.

Proof: We know that $\mathbb{E}[|\mathcal{Z}_{m,t}|]$ can be written as the follows,

(16)		$\displaystyle\mathbb{E}[|\mathcal{Z}_{m,t}|]$	$\displaystyle=\sum_{i=1}^{n}1\cdot\frac{m}{n}\frac{p_{i,t}}{k}$
(17)			$\displaystyle=\sum_{i=1}^{n}\frac{b}{n}p_{i,t}$
(18)			$\displaystyle\leq\sum_{i=1}^{n}\frac{b}{n}=b$

Let us first understand the expression for $\tilde{\Delta}_{t}$. Note that $\bar{u}_{t}=\frac{1}{b}\sum_{l\in\mathcal{Z}_{m,t}u_{l}}$ and thus by definition has expected value of zero. (1) follows from this idea. (2) follows from introducing the next sampling probability of clients in the first and second rounds (combined).

(19)		$\displaystyle\mathbb{E}_{t}[\tilde{\Delta}_{t}]$	$\displaystyle=\mathbb{E}_{t}[\Delta_{t}+\bar{u}_{t}]$
(20)			$\displaystyle\overset{(1)}{=}\mathbb{E}_{t}[\Delta_{t}]$
(21)			$\displaystyle=\mathbb{E}_{t}[\frac{1}{b}\sum_{j\in\mathcal{Z}_{m.t}}\frac{\bar{g}_{j}(w_{t})}{p_{j,t}}]$
(22)			$\displaystyle=\mathbb{E}_{t}[\frac{1}{b}\mathbbm{1}[i\in\mathcal{Z}_{m,t}]\sum_{i=1}^{n}\frac{\bar{g}_{i}(w_{t})}{p_{i,t}}]$
(23)			$\displaystyle=\sum_{i=1}^{n}\bar{g}_{i}(w_{t})\frac{1}{bp_{i,t}}\mathbb{E}_{t}[\mathbbm{1}[i\in\mathcal{Z}_{m,t}]]$
(24)			$\displaystyle\overset{(2)}{=}\sum_{i=1}^{n}\bar{g}_{i}(w_{t})\frac{1}{bp_{i,t}}\frac{q_{i,t}p_{i,t}}{k}$
(25)			$\displaystyle=\sum_{i=1}^{n}\bar{g}_{i}(w_{t})\frac{1}{b}\frac{m}{nk}$
(26)			$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\bar{g}_{i}(w_{t})=\bar{\Delta}_{t}$

We need to find an optimal sampling mechanism for our proposed method that minimizes overall variance. Additional variance is introduced due to the partial participation of clients leading to an approximation of the overall objective. We first study the impact of uniformly choosing samples from the set in Theorem 5.1.

Proof: We define $\bar{\Delta}_{t}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\tilde{g}_{i}(w_{t})$. In the case all participants participate, we can see that $\bar{\Delta}_{t}=\tilde{\Delta}_{t}$. However, for partial client participation we see that $\bar{\Delta}_{t}=\sum_{i=1}^{n}\tilde{g}_{i}(w_{t})\neq\sum_{i\in\mathcal{i\in\mathcal{X}_{m,t}}}\tilde{g}_{i}(w_{t})=\tilde{\Delta}_{t}$. Thus, the randomness in partial client participation consists of client sampling, stochastic gradient, and privacy noise.

Due to the smoothness assumption on $F$ (by assumption  1), and taking the expectation of $F(w_{t+1})$ over the client sampling and at round $t$. Note $w_{t}$ is unaffected by the sampling at round $t$.

	$\displaystyle\mathbb{E}$	${}_{t}[F(w_{t+1})]$
		$\displaystyle\leq F(w_{t})+\langle\triangledown F(w_{t}),\mathbb{E}_{t}[w_{t+1}-w_{t}]\rangle+\frac{L}{2}\mathbb{E}_{t}[||w_{t+1}-w_{t}||^{2}]$
		$\displaystyle=F(w_{t})+\langle\triangledown F(w_{t}),\eta\mathbb{E}_{t}[\tilde{\Delta}_{t}]\rangle+\frac{L}{2}\eta^{2}\mathbb{E}_{t}[||\tilde{\Delta}_{t}||^{2}]$
		$\displaystyle=F(w_{t})+\langle\triangledown F(w_{t}),\eta\mathbb{E}_{t}[\Delta_{t}+\bar{u}_{t}]\rangle+\frac{L}{2}\eta^{2}\mathbb{E}_{t}[||\Delta_{t}+\bar{u}_{t}||^{2}]$

Here, $\bar{u}_{t}=\frac{1}{|\mathcal{Z}_{m,t}|}\sum_{i\in\mathcal{Z}_{m,t}}u_{i}$ and then $\bar{u}_{t}\sim\mathcal{N}(0,\sqrt{|\mathcal{Z}_{m,t}|}\sigma_{0}^{2})$. Further, $\Delta_{t}=\sum_{i\in\mathcal{Z}_{m,t}}\frac{\bar{g}_{i}(w_{t})}{nq_{i,t}p_{i,t}}$. We note that expectation over the randomness of client sampling and private Gaussian noise gives us $\mathbb{E}_{t}[\Delta_{t}+\bar{u}_{t}]=\sum_{i\in\mathcal{Z}_{m,t}}\mathbb{E}_{t}[\frac{\bar{g}_{i}(w_{t})}{bnq_{i,t}p_{i,t}}+\bar{u}_{t}]=\sum_{i\in\mathcal{Z}_{m,t}}\mathbb{E}_{t}[\frac{\bar{g}_{i}(w_{t})}{bnq_{i,t}p_{i,t}}]=\mathbb{E}_{t}[\Delta_{t}]$. Due to the independent Gaussian noise and expectation over its randomness, we have $\mathbb{E}_{t}[\bar{u}_{t}]=0$ and $\Delta_{t}\perp\!\!\!\perp\bar{u}_{t}\rightarrow\mathbb{E}_{t}[\langle\Delta_{t},\bar{u}_{t}\rangle]=0$.

Thus, $\mathbb{E}_{t}[||\Delta_{t}+\bar{u}_{t}||^{2}_{2}]=\mathbb{E}_{t}[||\Delta_{t}||_{2}^{2}+||\bar{u}_{t}||^{2}_{2}+2\langle\Delta_{t},\bar{u}_{t}\rangle]=\mathbb{E}_{t}[||\Delta_{t}||_{2}^{2}+||\bar{u}_{t}||^{2}_{2}]$ . Therefore,

	$\displaystyle\mathbb{E}$	${}_{t}[F(w_{t+1})]$
(34)			$\displaystyle=F(w_{t})-\eta_{t}||\triangledown F(w_{t})||^{2}_{2}+\underbrace{\langle\triangledown F(w_{t}),\eta_{t}\mathbb{E}_{t}[\Delta_{t}+\triangledown F(w_{t})]\rangle}_{A_{1}}$
		$\displaystyle+\frac{L}{2}\eta_{t}^{2}\underbrace{\mathbb{E}_{t}[||\Delta_{t}||^{2}]}_{A_{2}}+\underbrace{\frac{L}{2}\eta_{t}^{2}\mathbb{E}_{t}[||\bar{u}_{t}||^{2}]}_{A_{3}}$

Let us bound term $A_{3}$ first. We note that by our sampling technique, the expected batch size is $\mathbb{E}[|\mathcal{Z}_{m,t}|]\leq b$ (Lemma 4.1) and that $\bar{u}_{t}\sim\mathcal{N}(0,\sqrt{|\mathcal{Z}_{m,t}|}\sigma_{0}^{2}\mathbb{I}_{d})$.

(35)		$\displaystyle A_{3}$	$\displaystyle=\frac{L}{2}\eta_{t}^{2}\mathbb{E}_{t}[||\bar{u}_{t}||^{2}]$
(36)			$\displaystyle\overset{(1)}{=}\frac{L}{2}\eta_{t}^{2}\mathbb{E}_{t}[||\sum_{i=1}^{n}\mathbbm{1}[i\in\mathcal{Z}_{m,t}]\frac{u_{i}}{bp_{i,t}}||^{2}_{2}]$
(37)			$\displaystyle=\frac{L\eta_{t}^{2}}{2b^{2}}\sum_{i=1}^{n}\text{Pr}[i\in\mathcal{Z}_{m,t}]\mathbb{E}_{t}[||\frac{u_{i}}{p_{i,t}}||^{2}_{2}]$
(38)			$\displaystyle=\sum_{i=1}^{n}\frac{L\eta_{t}^{2}}{2b^{2}}\frac{p_{i,t}q_{i,t}}{kp_{i,t}^{2}}\mathbb{E}_{t}[||u_{i}||^{2}_{2}]$
(39)			$\displaystyle=\sum_{i=1}^{n}\frac{L\eta_{t}^{2}}{2bnp_{i,t}}d\sigma_{0}^{2}$

Here (1) is from the law of total expectation (or tower expression), (2) is due to $E[||x||_{2}^{2}]=E[\sum_{k=1}^{p}x_{i}^{2}]=p\sigma^{2}$ where $x_{i}\sim\mathcal{N}(0,\sigma^{2})$, (3) is by Jensen’s inequality for a concave function (squared root is concave) and the (4) follows from Lemma 4.1.

Let us now bound $A_{2}$ with the assumption that we sample with replacement.

(40)		$\displaystyle A_{2}$	$\displaystyle=\mathbb{E}_{t}[||\Delta_{t}||_{2}^{2}]$
(41)			$\displaystyle=\mathbb{E}_{t}[||\frac{1}{b}\sum_{j\in Z_{m,t}}\frac{\bar{g}_{j}(w_{t})}{p_{j,t}}||^{2}]$
(42)			$\displaystyle\overset{(1)}{=}\underbrace{\frac{1}{b^{2}}\mathbb{E}_{t}[||\sum_{j\in\mathcal{Z}_{m,t}}\sum_{r=1}^{K_{j}}\frac{\triangledown f_{j}(w_{t};x_{jr})-\triangledown f_{j}(w_{t})-\nu_{jr}}{p_{j,t}K_{j}}||_{2}^{2}]}_{B_{1}}$
(43)			$\displaystyle+\underbrace{\frac{1}{b^{2}}\mathbb{E}_{t}[||\sum_{j\in\mathcal{Z}_{m,t}}\frac{1}{p_{j,t}}\triangledown f_{j}(w_{t})||_{2}^{2}]}_{B_{2}}$

Here, (1) follows from the simple expression $E[||x||^{2}]=E[||x-E[x]||^{2}]+||E[x]||^{2}$. We first bound the first term $B_{1}$. Note, $\nu_{jr}$ is the factor clipped off by clipping s.t. $\nu_{jr}\coloneqq\triangledown f_{i}(w_{t},x_{jr}-\triangledown\bar{f}_{i}(w_{t},x_{jr}$. Here, $\bar{f}_{i}(w_{t},x_{jr}$ is the clipped form of $\triangledown f_{i}(w_{t},x_{jr}$. We assume $E_{t}[||\nu_{jr}||_{2}^{2}]\leq c_{\nu}^{2}$.

	$\displaystyle B_{1}$	$\displaystyle\overset{(1)}{=}\frac{1}{b^{2}}\mathbb{E}_{t}[||\sum_{i=1}^{n}\mathbbm{1}[i\in Z_{m,t}]\sum_{r=1}^{K_{i}}\frac{\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}}{p_{i,t}K_{i}}||^{2}]$
		$\displaystyle=\frac{1}{b^{2}}||\sum_{i=1}^{n}\mathbb{E}_{t}[\mathbbm{1}[i\in Z_{m,t}]\sum_{r=1}^{K_{i}}\frac{\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}}{p_{i,t}K_{i}}]||^{2}$
		$\displaystyle\overset{(2)}{=}\sum_{i=1}^{n}\text{Pr}[i\in Z_{m,t}]\mathbb{E}_{t}[||\frac{1}{bp_{i,t}K_{i}}\sum_{r=1}^{K_{i}}\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}||^{2}_{2}]$
		$\displaystyle=\sum_{i=1}^{n}\frac{p_{i,t}q_{i,t}}{k}\mathbb{E}_{t}[||\frac{1}{bp_{i,t}K_{i}}\sum_{r=1}^{K_{i}}[\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}]||^{2}_{2}$
(44)			$\displaystyle=\sum_{i=1}^{n}\frac{p_{i,t}q_{i,t}}{kb^{2}p_{i,t}^{2}K_{i}^{2}}\mathbb{E}_{t}[||\frac{1}{bp_{i,t}K_{i}}\sum_{r=1}^{K_{i}}[\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}]||^{2}_{2}$
(45)			$\displaystyle\leq\sum_{i=1}^{n}\frac{1}{bnp_{i,t}K_{min}^{2}}\mathbb{E}_{t}[||\frac{1}{bp_{i,t}K_{i}}\sum_{r=1}^{K_{i}}[\triangledown f_{i}(w_{t};x_{ir})-\triangledown f_{i}(w_{t})-\nu_{ir}]||^{2}_{2}$
(46)			$\displaystyle\overset{(3)}{\leq}\sum_{i=1}^{n}\frac{2K_{max}}{bnp_{i,t}K_{min}^{2}}(\sigma^{2}_{L}+c_{\nu}^{2})$

Here (1) rewrites the summation with the indicator variable trick, and in (2), we take the expected value of the indicator function (also equal to its probability). In (3), we use the inequality $E[||x_{1}+x_{2}+...+x_{n}||^{2}]\leq n(E[||x_{1}||^{2}]+...E[||x_{n}||^{2})$ and $E[||x_{1}-x_{2}||^{2}]\leq 2(E[||x_{1}||^{2}]+E[||x_{2}||^{2})$, assumption 2 and assume $K_{max}=\max_{i=1}^{n}K_{i}$ (achieved by clipping the number of clients per user) and $K_{min}=\min_{i=1}^{n}K_{i}$. The server broadcasts both $K_{max}$ and $K_{min}$. Clients limit their training to $K_{max}$ samples with repetition and ensure that at least $K_{min}$ samples (with replacement) are trained each time.

Let us bound $B_{2}$ now,

(47)		$\displaystyle B_{2}$	$\displaystyle=\frac{1}{b^{2}}\mathbb{E}_{t}[||\sum_{i=1}^{n}\mathbbm{1}[i\in\mathcal{Z}_{m,t}]\frac{1}{p_{i,t}}f_{i}(w_{t})||^{2}_{2}]$
(48)			$\displaystyle\overset{(1)}{=}\frac{1}{b^{2}}\sum_{i=1}^{n}\text{Pr}(i\in\mathcal{Z}_{m,t})E_{t}||\triangledown f_{i}(w_{t})||^{2}$
(49)			$\displaystyle=\sum_{i=1}^{n}\frac{p_{i,t}q_{i,t}}{kb^{2}p_{i,t}^{2}}E_{t}||\triangledown f_{i}(w_{t})||^{2}$
(50)			$\displaystyle=\sum_{i=1}^{n}\frac{1}{bnp_{i,t}}E_{t}||\triangledown f_{i}(w_{t})||^{2}$
(51)			$\displaystyle\overset{(2)}{\leq}\sum_{i=1}^{n}\frac{1}{bnp_{i,t}}((A^{2}+1)||\triangledown F(w_{t})||^{2}+\sigma^{2}_{G})$

where (1) follows from analysis similar to $B_{1}$ and cancellation of probabilities, (2) uses the inequality $E[||x_{1}+x_{2}+...+x_{n}||^{2}]\leq n(E[||x_{1}||^{2}]+...E[||x_{n}||^{2})$ and Assumption 3.

Now, we only need to bound $A_{1}$.

(52)		$\displaystyle A_{1}$	$\displaystyle=\langle\triangledown F(w_{t}),\eta_{t}\mathbb{E}_{t}[\Delta_{t}+\triangledown F(w_{t})]\rangle$
(53)			$\displaystyle=\langle\triangledown F(w_{t}),\eta_{t}\mathbb{E}_{t}[\sum_{i=1}^{n}\mathbbm{1}[i\in Z_{m,t}]\frac{-\bar{g}_{i}(w_{t})}{bp_{i,t}}+\triangledown F(w_{t})]\rangle$
		$\displaystyle=\langle\triangledown F(w_{t}),-\eta_{t}\mathbb{E}_{t}[\sum_{i=1}^{n}\mathbbm{1}[i\in Z_{m,t}]\sum_{r=1}^{K_{i}}\frac{-\triangledown f_{i}(w_{t};x_{ir})+\nu_{ir}}{bp_{i,t}K_{i}}$
	$\displaystyle+$	$\displaystyle\triangledown F(w_{t})]\rangle$
		$\displaystyle=\langle\triangledown F(w_{t}),\eta_{t}\sum_{i,r}^{n,K_{i}}\text{Pr}[i\in\mathcal{Z}_{m,t}]E_{t}[\frac{-\triangledown f_{i}(w_{t};x_{ir})+\nu_{ir}+\triangledown f_{i}(w_{t})}{bp_{i,t}K_{i}}]\rangle$
		$\displaystyle\overset{(1)}{\leq}\langle\sqrt{\eta_{t}}\triangledown F(w_{t}),\sum_{i,r}^{n,K_{i}}\frac{bp_{i,t}}{n}E_{t}[\frac{-\triangledown f_{i}(w_{t};x_{ir})+\nu_{ir}+\triangledown f_{i}(w_{t})}{\frac{K_{min}bp_{i,t}}{\sqrt{\eta_{t}}}}]\rangle$
(54)			$\displaystyle=\langle\sqrt{\eta_{t}}\triangledown F(w_{t}),\sum_{i,r}^{n,K_{i}}\frac{\sqrt{\eta_{t}}}{nK_{min}}E_{t}[-\triangledown f_{i}(w_{t};x_{ir})+\nu_{ir}+\triangledown f_{i}(w_{t})]\rangle$
(55)			$\displaystyle\overset{(2)}{\leq}\frac{\eta_{t}}{2}||\triangledown F(w_{t})||^{2}+\frac{\eta_{t}}{2nK_{min}}\cdot 2K_{max}n(\sigma_{L}^{2}+c_{\nu}^{2})$
(56)			$\displaystyle=\frac{\eta_{t}}{2}||\triangledown F(w_{t})||^{2}+\frac{\eta_{t}K_{max}}{K_{min}}(\sigma_{L}^{2}+c_{\nu}^{2})$

where (1) is a simple re-shuffling of constants and (2) uses the inequality $\langle a,b\rangle\leq\frac{1}{2}(||a||^{2}_{2}+||b||^{2}_{2})$ and the analysis used in $B_{1}$ based on $E[||x_{1}+x_{2}+...+x_{n}||^{2}]\leq n(E[||x_{1}||^{2}]+...E[||x_{n}||^{2})$.

Putting everything together, we get that,

(57)		$\displaystyle\mathbb{E}_{t}$	$\displaystyle[F(w_{t+1})]$
(58)			$\displaystyle\leq F(w_{t})-\frac{\eta_{t}}{2}(1-\sum_{i=1}^{n}\frac{L\eta_{t}(A^{2}+1)}{bnp_{i,t}})||\triangledown F(w_{t})||^{2}_{2}$
(59)			$\displaystyle+\frac{(\eta_{t}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2}))}{K_{min}}(1+\sum_{i=1}^{n}\frac{L\eta_{t}}{bnp_{i,t}K_{min}})$
(60)			$\displaystyle+\sum_{i=1}^{n}\frac{L\eta_{t}^{2}}{2bnp_{i,t}}(\sigma^{2}_{G}+d\sigma_{0}^{2})$

Re-arranging the terms, taking expectations for all the steps and summing from $0$ to $T-1$ steps (and canceling some terms), and dividing by $T$, we next get the following,

(61)		$\displaystyle\sum_{t=0}^{T-1}\mathbb{E}_{t}[||\triangledown F(w_{t})||^{2}](\frac{\eta}{2T}(1-\sum_{i=1}^{n}\frac{L\eta_{t}^{2}(A^{2}+1)}{bnp_{i,t}}))$
(62)		$\displaystyle\leq\frac{F(w_{0})-F(w_{T})}{T}+\sum_{t}^{T-1}\frac{(\eta_{t}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2}))}{TK_{min}}$
(63)		$\displaystyle+\sum_{t,i}^{T-1,n}\frac{L\eta_{t}^{2}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2})}{bnTp_{i,t}K_{min}^{2}}+\sum_{t,i}^{T-1,n}\frac{L\eta_{t}^{2}}{2bnTp_{i,t}}(\sigma^{2}_{G}+d\sigma_{0}^{2})$
(64)		$\displaystyle\overset{(1)}{\leq}\frac{F(w_{0})-F(w_{*})}{T}+\sum_{t}^{T-1}\frac{(\eta_{b}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2}))}{K_{min}\sqrt{t+1}T}$
(65)		$\displaystyle+\sum_{t,i}^{T-1,n}\frac{L\eta^{2}_{b}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2})}{bnTp_{i,t}K_{min}^{2}(t+1)}+\sum_{t,i}^{T-1,n}\frac{L\eta_{b}^{2}}{2bnp_{i,t}(t+1)T}(\sigma^{2}_{G}+d\sigma_{0}^{2})$
(66)		$\displaystyle\overset{(2)}{\leq}\frac{F(w_{0})-F(w_{*})}{T}+\frac{(2\eta_{b}K_{max}(\sigma^{2}_{L}+c_{\nu}^{2}))}{K_{min}\sqrt{T}}$
(67)		$\displaystyle+\underbrace{\frac{L\eta_{b}^{2}}{bnT}[\frac{K_{max}(\sigma_{L}^{2}+c_{\nu}^{2})}{K_{min}}+\frac{\sigma^{2}_{G}+d\sigma^{2}_{0}}{2}]}_{C_{1}}\sum_{t,i}\frac{1}{p_{t,i}(t+1)}$

Here, in (1) we assume that $\eta_{t}=\frac{\eta_{b}}{\sqrt{t+1}}$ where $\eta_{b}$ is the base learning rate. Also, we know that by definition, $F(w_{*})\leq F(w_{T+1})\rightarrow-F(w_{*})\geq-F(w_{T+1})$. (2) follows from the idea that $\sum_{t=0}^{T-1}\frac{1}{\sqrt{t-1}}\leq\int_{1}^{T-1}\frac{1}{\sqrt{t-1}}=2(\sqrt{T})-2\leq 2\sqrt{T}$.