일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- data maximization
- 딥러닝
- Analysis
- value shaping
- q-FedAvg
- Agnostic FL
- Differential Privacy
- 연합학습
- Fairness
- q-FFL
- deep learning
- FedProx
- OoDD
- FL
- 개인정보
- FedAvg
- OSR
- free rider
- Federated Learning
- Open Set Recognition
- 기계학습
- convergence
- ordered dropout
- DP
- ML
- Machine learning
- PPML
- 머신러닝
- OOD
- Federated Transfer Learning
- Today
- Total
Federated Learning
[ICML 2019] Agnostic FL - (5) 본문
논문 제목: Agnostic Federated Learning
출처: https://arxiv.org/abs/1902.00146
지난 포스트까지 해서 learning guarantee에 관한 내용은 모두 마쳤고, 이번 포스트부터는 objective function의 optimization에 관한 내용을 다루려고 합니다. (이전 글 보기) 지난 포스트의 마지막 부분에서 밝혔듯이, 앞으로는 objective function이 convex하다고 가정합니다. 또한, L¯Dλ(h)=L¯Dconv(λ)(h)임 고려하여 앞으로는 Λ가 convex set이라고 가정하겠습니다.
8. Optimization Algorithm
지금부터는 관습을 따르기 위하여 notation을 일부 고치도록 하겠습니다. 우선, 우리가 해결해야 할 문제는 다음과 같습니다.
min
그리고 우리가 조절해야 할 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에 관해서 조금 더 자세하게 살펴보도록 하겠습니다.
'Federated Learning > Papers' 카테고리의 다른 글
[ICML 2019] Agnostic FL - (7) (1) | 2022.11.18 |
---|---|
[ICML 2019] Agnostic FL - (6) (0) | 2022.11.17 |
[ICML 2019] Agnostic FL - (4) (0) | 2022.11.08 |
[ICML 2019] Agnostic FL - (3) (0) | 2022.11.07 |
[ICML 2019] Agnostic FL - (2) (1) | 2022.11.05 |