수렴·정지점·전역 최적해의 구별

무엇이 수렴하는지 먼저 쓰기

최적화 논문에서 수렴은 목적값·기울기 노름·반복점·분포·해 집합까지 거리 중 서로 다른 대상을 뜻할 수 있다. 유한한 종료 검사는 현재 계산에 대한 증거이며 자동으로 점근 정리가 되지는 않는다.

실습은 f=x²/2, f=(x²−1)²/4, f=exp(−x)를 비교한다. infimum은 모두 0이다. 파란 선은 기울기 절댓값, 주황 선은 infimum 대비 목적 오차다. 예제는 무차원이지만 두 세로 지표는 여전히 다르다. 기울기가 작아 보인다고 임의 목적함수의 목적 오차 상계가 생기지 않는다.

볼록 이차함수에서 연결되는 오차

f=x²/2에서는 기울기가 x, 유일한 최소점이 0이고 GD는 xₖ=(1−η)ᵏx₀다. 표시한 양의 보폭 범위에서 수축한다.

매개변수 거리·기울기·목적 오차가 이 관계로 연결되는 것은 이 함수가 강한 곡률을 갖기 때문이다. 임의 함수의 보편 항등식이 아니다. 일반적인 연결에는 강볼록성·오차 상계 조건·Polyak–Łojasiewicz 부등식 같은 추가 가정이 필요하다.

기울기 0인 극대점

Double well에서는

전역 최소점은 ±1이다. 정확히 0에서 시작하면 결정론적 GD의 모든 점이 0이다. 기울기와 보폭이 0이지만 목적 오차는 0.25이고 Hessian은 −1이다. 따라서 비볼록 문제의 일차 정지점은 전역 최적성 인증이 아니다.

가까운 비영 초기점이 최소점 쪽으로 이동하는 관찰도 정확한 0의 반례를 없애지 않는다. 초기화와 섭동 방식은 알고리즘 설명의 일부로 기록해야 한다.

목적 오차 감소와 최소점의 존재

지수함수는 x→∞에서만 infimum 0에 접근한다. 기울기 절댓값은 목적값과 같고 모든 유한 x에서 양수다. 양의 일정 학습률에서는 x가 ηexp(−x)만큼 증가한다. 만약 x가 유한한 극한을 가지면 증가량은 양의 상수로 접근하여 모순이다. 따라서 x는 유한한 점으로 수렴하지 않지만 목적값과 기울기는 0으로 간다.

아래로 유계인 목적값 감소와 기울기 소멸이 반복점의 유계성이나 최솟값 달성을 뜻하지 않는 예다. 더 강한 수렴 결론에는 compactness와 해 존재 가정 등을 따로 확인해야 한다.

직접 풀기와 종료 기준

이차함수에서 x₀=1,η=0.2,10회이면 기울기는 0.8¹⁰≈0.107374, 목적 오차는 약 0.005765다. 기울기가 더 작지만 목적 오차는 더 큰 double-well 원점과 비교하자.

정지점이 아닌 곳에서 η=0으로 두면 기울기는 비영인데 보폭이 0이다. 보폭만 보는 종료 검사가 왜 위험한지 설명한다. η>0이어도 학습률이 아주 작으면 작은 기울기 없이도 작은 이동량이 나온다.

해결기 결과를 보고할 때 목적함수·가능영역·정상성 노름·허용오차·전역 인증 유무를 명시하자. 유한 실행의 경험적 관찰과 전체 수열에 대한 정리도 구별해야 한다.

더 읽기: Bottou, Curtis와 Nocedal.