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/