함수의 L-Lipschitz 성질

이는 연속 함수가 가질 수 있는 하나의 성질이다. 이를 수식으로 나타내면 다음과 같다.

$$ distance(f(x), f(y)) \le L * distance(x, y) \;\; ^\forall x, y $$

만약 우리가 이 함수를 $f : \mathbb{R}^d \rightarrow \mathbb{R} $로 한정짓고 거리 함수를 유클리디안 거리로 정의하면 이 성질은 좀더 구체적으로 다음과 같이 적을 수 있다.

$$ |f(x) - f(y)|_2 \le L |x-y|_2 \;\; ^\forall x, y \in \mathbb{R}^d $$

이제 나는 least square regression에서 손실 함수의 도함수가 L-Lipschitz 성질을 따르며 L이 몇인지를 계산해볼 것이다. 먼저, 손실함수를 계산해보면 다음과 같다.

$$ f(x) = \frac{1}{N} \sum_{j=1}^N \left( a_j^\top x - b_j \right)^2 = \frac{1}{N} | Ax - b |_2^2 = \frac{1}{N} (Ax - b)^\top (Ax - b) $$

이를 미분해보면 다음과 같아진다.

$$ \nabla f(x) = \frac{1}{N} \frac{\partial}{\partial x} \left( x^\top A^\top A x - x^\top A^\top b - b^\top Ax + b^\top b \right) $$

$$ \nabla f(x) = \frac{1}{N} \left( 2 A^\top A x - 2 A^\top b \right) = \frac{2}{N} \left( A^\top \left( A x - b \right) \right)$$

이제 위 Lipschitz 식과 같게 만들어보자. 먼저 함수의 차이를 구한다.

$$ \nabla f(x) - \nabla f(y) = \frac{2}{N} \left( A^\top \left( Ax - b \right) - A^\top \left( Ay - b \right) \right) = \frac{2}{N} \left( A^\top A \left( x - y \right) \right) $$

그리고 norm의 성질을 이용하여 위 식과 같게 만들면 어느 부분이 L에 해당하는지 알 수 있게 된다.

$$ \left| \nabla f(x) - \nabla f(y) \right|_2 = \left| \frac{2}{N} \left( A^\top A \left( x - y \right) \right) \right|_2 \le \frac{2}{N} \left| A^\top A \right|_2 \left| x - y \right|_2 $$

즉, norm의 성질을 이용하면 도함수가 $\frac{2}{N} \left| A^\top A \right|_2$-Lipschitz 성질을 가짐을 알 수 있다. 좀 더 타이트한 부등식을 사용하면 L을 더 줄일 수도 있을 것이다.