[ICML 2019] Agnostic FL - (5)

논문 제목: Agnostic Federated Learning

출처: https://arxiv.org/abs/1902.00146

 

 지난 포스트까지 해서 learning guarantee에 관한 내용은 모두 마쳤고, 이번 포스트부터는 objective function의 optimization에 관한 내용을 다루려고 합니다. (이전 글 보기) 지난 포스트의 마지막 부분에서 밝혔듯이, 앞으로는 objective function이 convex하다고 가정합니다. 또한, $\mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) = \mathcal{L}_{\mathcal{\overline{D}}_{\text{conv} (\lambda)}} (h)$임 고려하여 앞으로는 $\Lambda$가 convex set이라고 가정하겠습니다.

 

8. Optimization Algorithm 

 

 지금부터는 관습을 따르기 위하여 notation을 일부 고치도록 하겠습니다. 우선, 우리가 해결해야 할 문제는 다음과 같습니다.

$$\min_{h \in \mathcal{H}} \max_{\lambda \in \text{conv}{(\Lambda)}} \left( \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + \gamma ||h|| - \mu \chi^2 (\lambda \parallel \overline{\textbf{m}}) \right)$$

그리고 우리가 조절해야 할 parameter는 hypothesis $h \in \mathcal{H}$와 mixture weight $\lambda \in \Lambda$, 이렇게 두 가지입니다. 여기에서, $h$ 대신 model의 weight $w \in \mathcal{W} \subset \mathbb{R}^n$에 기반하는 것으로 objective function을 다시 정의할 것입니다. (이는 $w$에 의하여 $h$가 formation될 것이라는 점을 고려하면 자연스럽습니다.)

$$L (w, \lambda) := \sum_{k=1}^p \lambda_k L_k (w), \text{ where } L_k (w) := \frac {1} {m_k} \sum_{i=1}^{m_k} \ell (h(x_{k,i}), y_{k,i})$$

즉, $w$에 해당하는 $h$에 대하여, $\mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h)$가 $L (w, \lambda)$로, $\mathcal{L}_{\hat{\mathcal{D}}_k}$가 $L_k (w)$로 다시 정의된 상황입니다. 추가적으로, regularization term들이 optimization을 하는 데에 있어 영향을 미치지는 않을 것이기 때문에, 이 부분은 잠시 고려하지 않기로 하겠습니다. 그러면 최종적으로 우리가 논의하고자 하는 문제는 다음과 같이 정리되는데, 이는 전형적인 minimax algorithm의 모습입니다.

$$\min_{w \in \mathcal{W}} \max_{\lambda \in \Lambda} L (w, \lambda)$$

 이 decision rule이 equilibrium에 도달하였을 때의 값을 각각 $w^* \in \mathcal{W}$, $\lambda^* \in \Lambda$라고 정의합시다. 즉, $\lambda^*$는 가장 objective function을 크게 만드는 mixture weight이고, $w^*$는 그 objective function을 최소화하는 weight입니다. 이때, $\lambda$가 $\lambda^*$로부터 멀어진다면, 당연히 objective function이 갖는 값은 커지게 될 것입니다. 이러한 맥락에서, $\lambda^*$는 $\Lambda$의 중심이라고 이야기할 수 있습니다. 또한, $w$가 $w^*$로부터 멀어질 때에도 마찬가지로 objective function이 갖는 값은 커지게 될 것입니다.

 

 이제, 이러한 setting 하에서 optimization을 수행하도록 하겠습니다. 우선, $w$에 대한 $L$의 gradient를 $\nabla_w L (w, \lambda)$로, $\lambda$에 대한 $L$의 gradient를 $\nabla_\lambda L (w, \lambda)$로 denote하겠습니다. 그리고 $\delta_w L (w, \lambda)$와 $\delta_\lambda L (w, \lambda)$는 각각 이들의 unbiased estimate라고 합시다. 다시 말해, $\mathbb{E}_\delta \left[ \delta_w L (w, \lambda) \right] = \nabla_w L (w, \lambda)$, $\mathbb{E}_\delta \left[ \delta_\lambda L (w, \lambda) \right] = \nabla_\lambda L (w, \lambda)$입니다. 이때, 저자들은 이러한 unbiased estimates에 접근할 수 있다는 가정 하에, $\text{STOCHASTIC-AFL}$이라는 optimization algorithm을 고안하였고, 이에 관한 pseudo code는 오른쪽 그림과 같습니다. (해당 pseudo code에서도 regularization term은 생략되어 있다는 점 참고 바랍니다.)

 

 다음은 convergence analysis를 위한 몇 가지 가정과 notation에 관한 이야기입니다. Convexity를 제외하고는 크게 문제되는 것들이 아니며, 이러한 가정에 기반하여 $\text{Theorem 5}$를 증명할 것입니다.

 

$\text{Properties 1}$

 

 objective function $L$, weight $w \in \mathcal{W}$, 그리고 mixture weight $\lambda$들의 집합 $\Lambda$는 다음 성질을 만족한다:

 

1. [Convexity]

 임의의 $\lambda \in \Lambda$에 대해서, $w \mapsto L (w, \lambda)$는 convex하다.

2. [Compactness]

 $\max_{\lambda \in \Lambda} ||\lambda||_2 \leq R_\Lambda$, $\max_{w \in \mathcal{W}} ||w||_2 \leq R_\mathcal{W}$를 만족하는 $R_\Lambda$, $R_\mathcal{W}$가 존재한다.

3. [Bounded Gradients]

 임의의 $w \in \mathcal{W}, \lambda \in \Lambda$에 대해서, $||\nabla_w L (w, \lambda)||_2 \leq G_w$, $||\nabla_\lambda L (w, \lambda)||_2 \leq G_\lambda$를 만족하는 $G_w$, $G_\lambda$가 존재한다.

4. [Stochastic Variance]

 임의의 $w \in \mathcal{W}, \lambda \in \Lambda$에 대해서, $\mathbb{E} \left[ ||\delta_w L (w, \lambda) - \nabla_w L (w, \lambda)||_2^2 \right] \leq \sigma_w^2$, $\mathbb{E} \left[ ||\delta_\lambda L (w, \lambda) - \nabla_\lambda L (w, \lambda)||_2^2 \right] \leq \sigma_\lambda^2$를 만족하는 $\sigma_w^2$, $\sigma_\lambda^2$가 존재한다.

5. [Notation]

 $U_w$는 $\delta_w L (w, \lambda)$에 대한 시간복잡도, $U_\lambda$는 $\delta_\lambda L (w, \lambda)$에 대한 시간복잡도, 그리고 $U_p$는 projection에 대한 시간복잡도를 의미한다. 추가적으로, $d := \dim{\mathcal{W}}$이다.

 

$\text{Theorem 5}$

 

 $\text{Properties 1}$이 성립한다고 가정하자. 그리고 $\text{STOCHASTIC-AFL}$ 알고리즘이 반환한 값을 각각 $w^A$, $\lambda^A$라고 하자. 이때, step size $\gamma_w := \frac {2 R_\mathcal{W}} {\sqrt{T (\sigma_w^2 + G_w^2)}}$, $\gamma_\lambda := \frac {2 R_\Lambda} {\sqrt{T (\sigma_\lambda^2 + G_\lambda^2)}}$에 대해서, 해당 알고리즘은 다음과 같은 convergence guarantee를 갖는다:

$$\mathbb{E} \left[ \max_{\lambda \in \Lambda} L (w^A, \lambda) - \min_{w \in \mathcal{W}} \max_{\lambda \in \Lambda} L (w, \lambda) \right] \leq \frac {3 R_\mathcal{W} \sqrt{\sigma_w^2 + G_w^2}} {\sqrt{T}} + \frac {3 R_\Lambda \sqrt{\sigma_\lambda^2 + G_\lambda^2}} {\sqrt{T}}$$

그리고, 해당 알고리즘의 시간복잡도는 $\mathcal{O} \left( (U_\lambda + U_w + U_p + d + k) T\right)$이다.

 

$\text{Proof}$

 $\text{Properties 1}$에 의하여 $L$은 $w$에 convex하다. 또한, $L$은 $\lambda$에 linear하므로,  $L$은 $\lambda$에 concave하기도 하다. 따라서 다음과 같은 부등식이 성립한다:

$$\begin{align*} \max_{\lambda \in \Lambda} L (w^A, \lambda) - \min_{w \in \mathcal{W}} \max_{\lambda \in \Lambda} L (w, \lambda) &= \max_{\lambda \in \Lambda} L (w^A, \lambda) -  \max_{\lambda \in \Lambda} \min_{w \in \mathcal{W}} L (w, \lambda) \; (\because \text{Minimax Theorem}) \\&\leq \max_{\lambda \in \Lambda} \left\{ L (w^A, \lambda) - \min_{w \in \mathcal{W}} L (w, \lambda^A) \right\} \; (\because \text{subadditivity of $\max$}) \\&= \max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \left\{ L (w^A, \lambda) - L (w, \lambda^A) \right\} \\&\leq \frac {1} {T} \underbrace{\max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \left\{ \sum_{t=1}^T L (w_t, \lambda) - L (w, \lambda_t) \right\}}_{=: \mathcal{A}} \\&\quad (\because \text{convexity in $w$ and linearity in $\lambda$}) \end{align*}$$

 

같은 이유로, 다음이 성립한다:

$$\begin{align*} L (w_t, \lambda) - L (w, \lambda_t) &=  L (w_t, \lambda) -  L (w_t, \lambda_t) + L (w_t, \lambda_t) - L (w, \lambda_t) \\&\leq (\lambda - \lambda_t) \nabla_\lambda L (w_t, \lambda_t) + (w_t - w) \nabla_w L (w_t, \lambda_t)) \; (\because \text{definition of $\nabla_\lambda$ and $\nabla_w$}) \\&= (\lambda - \lambda_t) \nabla_\lambda L (w_t, \lambda_t) + (w_t - w) \nabla_w L (w_t, \lambda_t)) \\&\quad + (\lambda - \lambda_t) \delta_\lambda L (w_t, \lambda_t) - (\lambda - \lambda_t) \delta_\lambda L (w_t, \lambda_t) \\&\quad + (w_t - w) \delta_w L(w_t, \lambda_t) - (w_t - w) \delta_w L(w_t, \lambda_t) \\&= (\lambda - \lambda_t) \delta_\lambda L (w_t, \lambda_t) + (w_t - w) \delta_w L(w_t, \lambda_t) \\&\quad + (\lambda - \lambda_t) \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) \\&\quad + (w_t - w) \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \\&= (\lambda - \lambda_t) \delta_\lambda L (w_t, \lambda_t) + (w_t - w) \delta_w L(w_t, \lambda_t) \\&\quad + \lambda \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) - w \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \\&\quad + \lambda_t \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) - w_t \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \end{align*}$$

 

따라서, $\mathcal{A}$는 다음과 같이 세 개의 term으로 bounded되며, 이제부터 각각을 bound할 것이다.

$$\begin{align*} \mathcal{A} &:= \max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \left\{ \sum_{t=1}^T L (w_t, \lambda) - L (w, \lambda_t) \right\} \\&\leq \underbrace{\max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \sum_{t=1}^T \left\{ (\lambda - \lambda_t) \delta_\lambda L (w_t, \lambda_t) + (w_t - w) \delta_w L(w_t, \lambda_t) \right\}}_{=: \mathcal{A}_1} \\&\quad + \underbrace{\max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \sum_{t=1}^T \left\{ \lambda \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) - w \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \right\}}_{=: \mathcal{A}_2} \\&\quad + \underbrace{\max_{\substack{\lambda \in \Lambda \\ w \in \mathcal{W}}} \sum_{t=1}^T \left\{ \lambda_t \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) - w_t \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \right\}}_{=: \mathcal{A}_3} \end{align*}$$

 

 우선, $\mathcal{A}_1$을 살펴보자. $\mathcal{A}_1$의 왼쪽 term은 다음과 같이 정리된다:

$$\begin{align*} \sum_{t=1}^T (w_t - w) \delta_w L(w_t, \lambda_t) &= \frac {1} {2 \gamma_w} \sum_{t=1}^T 2 \gamma_w (w_t - w) \delta_w L(w_t, \lambda_t) \\&= \frac {1} {2 \gamma_w} \sum_{t=1}^T \left[ ||(w_t - w)||_2^2 + ||\gamma_w \delta_w L(w_t, \lambda_t)||_2^2 - ||(w_t - w) - \gamma_w \delta_w L(w_t, \lambda_t)||_2^2 \right] \\&\quad (\because X^2 + Y^2 - (X - Y)^2 = 2 XY) \\&= \frac {1} {2 \gamma_w} \sum_{t=1}^T \left[ ||(w_t - w)||_2^2 + \gamma_w^2 ||\delta_w L(w_t, \lambda_t)||_2^2 - ||(w_t - \gamma_w \delta_w L(w_t, \lambda_t) - w||_2^2 \right] \\&\leq \frac {1} {2 \gamma_w} \sum_{t=1}^T \left[ ||(w_t - w)||_2^2 + \gamma_w^2 ||\delta_w L(w_t, \lambda_t)||_2^2 - ||(w_{t+1} - w)||_2^2 \right] \\&\quad (\because w_t := \text{Project} (w_{t-1} - \gamma_w \delta_w L(w_{t-1}, \lambda_{t-1}, \mathcal{W}))) \\&= \frac {1} {2 \gamma_w} \sum_{t=1}^T \left[ ||(w_t - w)||_2^2 - ||(w_{t+1} - w)||_2^2 \right] + \frac {1} {2 \gamma_w} \sum_{t=1}^T \gamma_w^2 ||\delta_w L(w_t, \lambda_t)||_2^2 \\&= \frac {1} {2 \gamma_w} \left[ ||(w_1 - w)||_2^2 - ||(w_{T+1} - w)||_2^2 \right] + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \\&\leq \frac {1} {2 \gamma_w} ||(w_1 - w)||_2^2 + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \\&= \frac {1} {2 \gamma_w} \left[ ||w_1||_2^2 - 2 w_1 \cdot w + ||w||_2^2 \right] + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \\&\leq \frac {4R_\mathcal{W}^2} {2 \gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \; (\because \max_{w \in \mathcal{W}} ||w||_2 \leq R_\mathcal{W}??????) \\&=  \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t) - \nabla L (w_t, \lambda_t) + \nabla L (w_t, \lambda_t)||_2^2      \end{align*}$$

따라서,

$$\begin{align*} \mathbb{E} \left[ \max_{w \in \mathcal{W}} \sum_{t=1}^T (w_t - w) \delta_w L(w_t, \lambda_t) \right] &\leq \mathbb{E} \left[ \max_{w \in \mathcal{W}} \left( \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \right) \right] \\&= \mathbb{E} \left[ \frac {2R_\mathcal{W}^2} {\gamma_w} \right] + \frac {\gamma_w} {2} \mathbb{E} \left[ \sum_{t=1}^T ||\delta_w L(w_t, \lambda_t)||_2^2 \right] \; (\because \text{there is no $w$ term}) \\&= \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T  \mathbb{E} \left[ ||\delta_w L(w_t, \lambda_t)||_2^2 \right] \; (\because \text{expectation is linear}) \\&= \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T  \mathbb{E} \left[ ||\delta_w L(w_t, \lambda_t) - \nabla L (w_t, \lambda_t) + \nabla L (w_t, \lambda_t)||_2^2 \right] \\&= \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T \mathbb{E} \left[ ||\delta_w L(w_t, \lambda_t) - \nabla L (w_t, \lambda_t)||_2^2 \right] \\&\quad + \frac {\gamma_w} {2} \sum_{t=1}^T \mathbb{E} \left[ \left( \delta_w L(w_t, \lambda_t) - \nabla L (w_t, \lambda_t) \right) \cdot \nabla L (w_t, \lambda_t) \right] \\&\quad + \frac {\gamma_w} {2} \sum_{t=1}^T \mathbb{E} \left[ ||\nabla L (w_t, \lambda_t)||_2^2 \right] \; (\because (X + Y)^2 = X^2 + 2 XY + Y^2) \\&= \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \sum_{t=1}^T \mathbb{E} \left[ ||\delta_w L(w_t, \lambda_t) - \nabla L (w_t, \lambda_t)||_2^2 \right] \\&\quad + \frac {\gamma_w} {2} \sum_{t=1}^T \mathbb{E} \left[ ||\nabla L (w_t, \lambda_t)||_2^2 \right] \; (\because \mathbb{E} [\delta_w L(w_t, \lambda_t)] = \nabla_w L(w_t, \lambda_t)) \\&\leq \frac {2R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w} {2} \times T \times \sigma_w^2 + \frac {\gamma_w} {2} \times T \times G_w^2 \; (\because \text{Properties 1}) \\&= \frac {2 R_\mathcal{W}^2} {\gamma_w} + \frac {\gamma_w T \sigma_w^2} {2} + \frac {T \gamma_w G_w^2} {2}  \end{align*}$$

이며, $\mathcal{A}_1$의 오른쪽 term도 동일한 방식으로 다음과 같이 정리된다:

$$\mathbb{E} \left[ \max_{\lambda \in \Lambda} \sum_{t=1}^T (\lambda_t - \lambda) \delta_\lambda L(w_t, \lambda_t) \right] \leq \frac {2 R_\mathcal{\Lambda}^2} {\gamma_\lambda} + \frac {\gamma_\lambda T \sigma_\lambda^2} {2} + \frac {T \gamma_\lambda G_\lambda^2} {2}$$

 

 다음으로, $\mathcal{A}_2$를 살펴보자. $\mathcal{A}_2$의 왼쪽 term의 경우, Cauchy-Schwarz inequality에 의하여 다음이 성립한다:

$$\begin{align*} \max_{\lambda \in \Lambda} \left\{ \sum_{t=1}^T \lambda \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) \right\} &\leq \max_{\lambda \in \Lambda} \left\{ \sum_{t=1}^T ||\lambda||_2 \cdot || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2 \right\} \\&\leq R_\Lambda \sum_{t=1}^T || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2 \; (\because \text{Properties 1})  \end{align*}$$

따라서, 양변에 expectation을 취해주면, 다음 결과를 얻을 수 있다:

$$\begin{align*} \mathbb{E} \left[ \max_{\lambda \in \Lambda} \left\{ \sum_{t=1}^T \lambda \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) \right\} \right] &\leq \mathbb{E} \left[ R_\Lambda \sum_{t=1}^T || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2 \right] \\&= R_\Lambda \cdot \mathbb{E} \left[ \sum_{t=1}^T || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2 \right] \\&= R_\Lambda \cdot \mathbb{E} \left[ \left( \sum_{t=1}^T || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2 \right)^{2 \cdot \frac {1} {2}} \right] \\&\leq R_\Lambda \cdot \left( \mathbb{E} \left[ \sum_{t=1}^T || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2^2 \right] \right)^{\frac {1} {2}} \\&\quad (\because \text{Jensen's inequality}) \\&= R_\Lambda \cdot \left( \left[ \sum_{t=1}^T \mathbb{E} || \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) ||_2^2 \right] \right)^{\frac {1} {2}} \\&\quad (\because \text{expectation is linear}) \\&\leq R_\Lambda \sqrt{T \sigma_w^2} \\&= R_\Lambda \sqrt{T} \sigma_w   \end{align*}$$

그리고 $\mathcal{A}_2$의 오른쪽 term도 동일한 방식으로 다음과 같이 정리된다:

$$\max_{w \in \mathcal{W}} \left\{ \sum_{t=1}^T w \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \right\} \leq R_\mathcal{W} \sqrt{T} \sigma_w$$

 

 마지막으로, $\mathcal{A}_3$의 경우, $\mathbb{E} [\delta_w L(w_t, \lambda_t)] = \nabla_w L(w_t, \lambda_t)$, $\mathbb{E} [\delta_\lambda L(w_t, \lambda_t)] = \nabla_\lambda L(w_t, \lambda_t)$이므로, expectation을 취하면 0이 된다. 다시 말해, 

$$\mathbb{E} \left[ \sum_{t=1}^T \left\{ \lambda_t \left( \nabla_\lambda L (w_t, \lambda_t) - \delta_\lambda L (w_t, \lambda_t) \right) - w_t \left( \nabla_w L (w_t, \lambda_t) - \delta_w L (w_t, \lambda_t) \right) \right\} \right] = 0$$

이다. 따라서, 위 세 가지를 모두 종합하면 다음과 같은 결론을 얻을 수 있다:

$$\begin{align*} \mathbb{E} \left[ \max_{\lambda \in \Lambda} L (w^A, \lambda) - \min_{w \in \mathcal{W}} \max_{\lambda \in \Lambda} L (w, \lambda) \right] &\leq \mathbb{E} \left[ \frac {1} {T} \mathcal{A} \right] \leq \frac {1} {T} \mathbb{E} \left[ \mathcal{A}_1 \right] + \frac {1} {T} \mathbb{E} \left[ \mathcal{A}_2 \right] + \frac {1} {T} \mathbb{E} \left[ \mathcal{A}_3 \right] \\&\leq \left[ \frac {2 R_\mathcal{W}^2} {T \gamma_w} + \frac {\gamma_w \sigma_w^2} {2} + \frac {\gamma_w G_w^2} {2} \right] + \left[ \frac {2 R_\mathcal{\Lambda}^2} {T \gamma_\lambda} + \frac {\gamma_\lambda \sigma_\lambda^2} {2} + \frac {\gamma_\lambda G_\lambda^2} {2} \right] \\&\quad + \left[ \frac{R_\Lambda \sigma_\lambda} {\sqrt{T}} \right]  + \left[ \frac{R_\mathcal{W} \sigma_w} {\sqrt{T}} \right] + 0 \\&= \frac {2 R_\mathcal{W}^2} {T \gamma_w} + \frac {\gamma_w (\sigma_w^2 + G_w^2)} {2} + \frac {2 R_\mathcal{\Lambda}^2} {T \gamma_\lambda} + \frac {\gamma_\lambda (\sigma_\lambda^2 + G_\lambda^2)} {2} \\&\quad + \frac{R_\Lambda \sigma_\lambda} {\sqrt{T}} + \frac{R_\mathcal{W} \sigma_w} {\sqrt{T}} \end{align*}$$

위 식에 주어진 step size $\gamma_w := \frac {2 R_\mathcal{W}} {\sqrt{T (\sigma_w^2 + G_w^2)}}$, $\gamma_\lambda := \frac {2 R_\Lambda} {\sqrt{T (\sigma_\lambda^2 + G_\lambda^2)}}$를 대입하는 것으로 증명을 마무리한다. $\square$

 

 $\text{Theorem 5}$이 보장하는 convergence는 $\sigma_w^2$와 $\sigma_\lambda^2$, 즉, stochastic gradient의 variance에 의존하고 있습니다. 다음 포스트에서는 이 stochastic gradient에 관해서 조금 더 자세하게 살펴보도록 하겠습니다.