Strong convexity와 optimal point 분석

Convex 함수에서 first order 조건식은 다음과 같다.

$$ f(y) \ge f(x) + \nabla f^\top (x) (y - x) $$

여기서 더해서 우리는 convex 함수의 Hessian이 positive semi-difinite라는 성질을 이용할 수 있다. 즉, $ \nabla^2 f(x) \succeq 0 $이고 $ v^\top \nabla^2 f(x) v \ge 0 \;\; ^\forall v \in \mathbb{R}^d $임이 만족한다. 이를 이용해서, 우리는 위 부등식을 등식으로 변환할 수 있다. 어떤, 임의의 $z$를 도입하여 등식으로 변환한다.

$$ f(y) = f(x) + \nabla f^\top (x) (y - x) + \frac{1}{2} (y-x)^\top \nabla^2 f(z) (y-x) $$

만약, 함수 f가 strong duality를 만족한다고 가정하면 아래와 같이 적을 수 있다.

$$ \nabla^2 f(z) \succeq mI $$

이는 아래와 같은 식을 만족한다는 뜻이다.

$$ v^\top \left( \nabla^2 f(z) - mI \right) v \ge 0 \; \; ^\forall v \in \mathbb{R}^d $$

이 부등식은 모든 $v$에 대해서 성립하므로 $v=y-x$로 생각하고 부등식을 적어본다.

$$ (y-x)^\top \nabla^2 f(z) (y-x) \ge (y-x)^\top mI (y-x) = m |y-x|_2^2 $$

이를 이용해서 다시 부등식으로 변환하면 다음과 같아진다.

$$ f(y) \ge f(x) + \nabla f^\top (x) (y - x) + \frac{m}{2} |y-x|_2^2 $$

여기서부터 중요한데, 이제 $ f(x) + \nabla f^\top (x) (y-x) + \frac{m}{2} |y-x|_2^2 $가 우리가 최적화하고자 하는 함수의 lower bound로써의 역할을 하게 된다. 이제 $x$가 고정되었을 때, lower bound가 최소가 되는 $\tilde{y}$를 구하는 것이다.

$$ \frac{\partial}{\partial y} \left( f(x) + \nabla f^\top (x) (y-x) + \frac{m}{2} |y-x|_2^2 \right) = \nabla f(x) + m (y-x) $$

$$ \nabla f(x) + m (\tilde{y}-x) = 0 $$

$$ \tilde{y} = x - \frac{1}{m} \nabla f(x) $$

이 $\tilde{y}$를 오른쪽 항에만 집어넣으면 우리가 도달할 수 있는 가장 낮은 lower bound를 계산할 수 있다.

$$ f(y) \ge f(x) + \nabla f^\top (x) \left( - \frac{1}{m} \nabla f(x) \right) + \frac{m}{2} \left| -\frac{1}{m} \nabla f(x) \right|_2^2 $$

$$ f(y) \ge f(x) - \frac{1}{m} \left| \nabla f(x) \right|_2^2 + \frac{m}{2m^2} \left| \nabla f(x) \right|_2^2 = f(x) - \frac{1}{2m} \left| \nabla f(x) \right|_2^2 $$

이 lower bound는 가장 낮은 lower bound이기 때문에 optimal objective value도 만족한다는 특성이 있다. 이 말이 맞는 건지 의문이 들 수 있는데, 나는 이렇게 결론내렸다. 근본적으로 $y$가 변해도 $y$에 대한 함수가 lower bound라는 사실은 변하지 않는다. 그리고 우리는 $y$에 대한 함수를 최적화했기 때문에 이런 식으로 표현이 가능하다.

$$ p^* = f(x^*) \ge f(x) + \nabla f^\top (x) (x^* - x) + \frac{m}{2} |x^*-x|_2^2 \ge f(x) - \frac{1}{2m} \left| \nabla f(x) \right|_2^2 $$

이를 이용하면 gradient의 크기와 optimal value와의 가까운 정도를 예측해볼 수 있다.

$$ \frac{1}{2m} \left| \nabla f(x) \right|_2^2 \ge f(x) - p^* $$

여기서 optimal value와 현재의 value인 $f(x)$의 차이가 gradient의 크기의 제곱의 $\frac{1}{2m}$배보다 작다는 것을 알 수 있다. 이 식의 한계점은 함수가 strongly convex여야한다는 것이다.

여기서 더 나아가서 우리는 optimal variable과 현재 variable간의 차이 또한 gradient의 크기를 기반으로 upper bound를 계산할 수 있다. 제일 간단한 방법은 코시 슈바르츠 부등식을 이용하는 것이다. 코시 슈바르츠를 가장 간단하게 생각하는 방법은 내적 값의 최솟값을 고려하는 것이다. ($ x^\top y \ge |x||y|cos(\pi) = -|x||y| $)

$$ f(x^*) \ge f(x) + \nabla f^\top (x) (x^* - x) + \frac{m}{2} |x^*-x|_2^2 \ge f(x) - \left| \nabla f (x) \right|_2 \left| (x^* - x) \right|_2 + \frac{m}{2} |x^*-x|_2^2 $$

우리는 그리고 가장 간단한 $f(x) \ge f(x^*)$를 이용해서 다시 생각할 수 있다.

$$ 0 \ge f(x^*) - f(x) \ge - \left| \nabla f (x) \right|_2 \left| (x^* - x) \right|_2 + \frac{m}{2} |x^*-x|_2^2 $$

$$ \left| \nabla f (x) \right|_2 \left| (x^* - x) \right|_2 \ge \frac{m}{2} |x^*-x|_2^2 $$

$$ \frac{2}{m} \left| \nabla f (x) \right|_2 \ge |x^*-x|_2 $$

이로써, optimal variable과 현재 variable 간의 차이는 gradient의 크기의 $\frac{2}{m}$배보다 작다는 것을 알 수 있다.