06-03-04 Convergence analysis under strong convexity · 모두를 위한 컨벡스 최적화

[utterances-bot]

06-03-04 Convergence analysis under strong convexity · 모두를 위한 컨벡스 최적화

https://convex-optimization-for-all.github.io/contents/chapter06/2021/03/20/06_03_04_convergence_analysis_under_strong_convexity/

[sangyeon-park]

증명 중간에 gradient descent 는
\begin{align}
f(x) - f(x^{*}) \le \frac{1}{2m} \lVert \nabla f(x) \rVert^2_2 \
\end{align}
를 만족해야 한다고 하셨는데, 혹시 왜 그런지 알 수 있을까요?

[magatriod7]

위에 있는분 이미 늦었을 것 같지만 제가 찾아본 바로는
𝑓(𝑦)≥𝑓(𝑥)+∇𝑓(𝑥)^𝑇 (𝑦−𝑥)+𝑚/2 ‖𝑦−𝑥‖_2^2에서 우항의 최소값을 y에 대입하면 항상 그 값이 성립하게 되는데 우항의 (y-x)를 Q로 치환해서 미분한 후 그 최소값을 가질 때의 y와 x의 관계를 구하면
𝑦=𝑥−1/𝑚 ∇𝑓(𝑥)를 만족할 때 우항이 최소값을 가지게 됩니다.

이 값을 대입하면 𝑓(𝑥)−1/2𝑚 ‖∇𝑓(𝑥)‖_2^2가 나오고 이것이 우항에서 나올 수 있는 가장 작은 값이고 f(y)는 항상 이것보다 크기 때문에

𝑓(𝑦)≥𝑓(𝑥)−1/2𝑚 ‖∇𝑓(𝑥)‖_2^2를 만족한다고 합니다.

[magatriod7]

위에 정정하겠습니다. 2번째 줄 우항의 최소값을 y에 대입한다는 것이 아니라 우항의 최소값이 나올 때의 y를 대입한다는 이야기였습니다.

[sangyeon-park]

@magatriod7 오 그렇군요... 친절한 설명 감사드립니다!