f=xy일 때 min,max f(x,y) evaluation 하는 법 - Assignment 3 GAN Inline Question 1
f=xy일 때 min,max f(x,y) evaluation 하는 법 - Assignment 3 GAN Inline Question 1
Generative_Adversarial_Networks - Inline Question 1
We will look at an example to see why alternating minimization of the same objective (like in a GAN) can be tricky business.
Consider $f(x,y)=xy$. What does $\min_x\max_y f(x,y)$ evaluate to?
(Hint: minmax tries to minimize the maximum value achievable.)
Now try to evaluate this function numerically for 6 steps, starting at the point $(1,1)$, by using alternating gradient (first updating y, then updating x using that updated y) with step size $1$.
**Here step size is the learning_rate, and steps will be learning_rate$\times$gradient.**
You'll find that writing out the update step in terms of $x_t,y_t,x_{t+1},y_{t+1}$ will be useful.
Breifly explain what $\min_x\max_y f(x,y)$ evaluates to and record the six pairs of explicit values for $(x_t,y_t)$ in the table below.
### Your answer: $$y_{t+1} = y_t + \frac{df}{dy} = y_t+x_t$$ $$x_{t+1} = x_t - \frac{df}{dx} = -y_{t+1}$$ where $ f=x_t \cdot y_{t+1}$
y0 |
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
1 |
2 |
0 |
0 |
0 |
0 |
0 |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
1 |
-2 |
0 |
0 |
0 |
0 |
0 |
GAN의 어려움을 보기 위해 제안된 function으로 minimax 관계에 따른 어려움을 보기 위해 고안된 문제입니다.
이 문제를 함에 있어 순서가 중요한데 $min_x$보다 $max_y$가 먼저 일어난다는 사실을 알고 진행합시다.
문제에서 step_size가 learning_rate이고 step은 learning_rate*gradient라고 명시하였기에 이에 대한 y를 maximize하는 방법은 -minimize하는 방식이라고 생각할 수 있습니다.
이에 따른 수식은 다음과 같습니다.
$$y_{t+1} = y_t + \frac{df}{dy} = y_t+x_t$$
그러나 이후 minimize를 할 때는 f의 상황이 달라집니다. 왜냐하면 y에 따른 update를 했고 이에 따른 f는 다음 y의 값을 곱한 것이 되니까요.
$$ f=x_t \cdot y_{t+1}$$
여기서 f에 대한 미분을 해야하고 이에 대한 식은 결국 다음과 같이 될 것입니다.
이에 대해 참조한 reddit 질의 응답글을 참조하시길 바랍니다.
https://www.reddit.com/r/cs231n/comments/9biqyl/inline_question_1_for_gans_in_assignment_3/e55vquk/
