SVRG·Control Variate와 분산 감소

평균 방향을 보존하면서 잡음을 줄이기

Control variate는 상관된 양을 빼고 그 알려진 기대값을 다시 더한다. 원하는 평균을 유지하면서 분산을 줄이는 원리다. 유한합 최적화에서는 같은 성분의 기울기를 가까운 두 점에서 계산하면 강한 상관을 얻을 수 있다.

실습은 fᵢ(x)=hᵢ(x−aᵢ)²/2, h=(1,2,3,4), a=(−1,1,2,0)를 사용한다. 전체 기울기는 G(x)=2.5x−1.75이므로 최적점은 0.7이다. 성분별 최적점이 다르므로 전체 최적점에서 개별 기울기가 모두 0일 필요는 없다.

SVRG 추정량의 유도

Anchor x̃에서 전체 기울기를 한 번 계산한 뒤 균등 성분 하나를 고른다.

두 성분 기울기는 같은 인덱스를 사용한다. 관계없는 성분을 빼도 추가 독립 가정 아래 평균이 맞을 수 있지만 공분산이 달라져 의도한 상쇄가 사라진다.

이 이차 모형에서는 target에 의존하는 항이 정확히 상쇄된다.

1.25는 곡률 h의 모집단 분산이다. 이 식은 현재 문제족에서 유도한 것이며 모든 SVRG 문제의 정확한 분산 공식은 아니다.

세 가지 anchor 예제

x=x̃=0.7이면 모든 SVRG 추정량이 0이다. SGD 기울기는 (1.7,−0.6,−3.9,2.8)로 평균 0, 분산 6.575다. 성분들이 같은 최소점을 공유하지 않기 때문에 최적점에도 잡음이 남는다.

x=0.7을 유지하고 anchor를 −1로 옮기면 분산은 1.25·1.7²=3.6125다. 여전히 비편향이지만 같은 anchor보다 시끄럽다. 임의로 먼 anchor에서는 보통 SGD보다 분산이 커질 수도 있다. 이름이 variance reduction이라고 모든 점 쌍에서 분산 감소를 보장하는 것은 아니다.

x=x̃=2로 바꾸면 SVRG 분산은 0인데 모든 추정량이 3.25다. 정확하지만 비영인 기울기다. 따라서 분산 0은 최적성 인증과 다르다.

계산 비용과 바깥 반복

그림은 한 현재 점·anchor 쌍에서 가능한 네 성분 추정량을 비교한다. 완전한 SVRG 학습 실행이 아니다. G(x̃)를 계산하려면 여기서는 네 성분 평가가 든다. 내부 보폭도 anchor 정보를 저장하지 않으면 보통 현재 점과 anchor에서 두 기울기를 평가한다. 여러 내부 보폭에 걸쳐 전체 기울기 비용을 분산시키고 anchor 갱신 주기를 명시해야 한다.

수렴률에는 성분 손실의 smoothness, 적절한 볼록성 또는 비볼록 정상성 목표, 학습률 등의 가정이 더 필요하다. 한 보폭의 낮은 분산만으로 전체 계산량과 최종 정확도가 정해지지 않는다.

직접 풀기와 풀이

x=0.7,x̃=−1, 선택 성분 0이면 SGD 기울기는 1.7, SVRG 추정량은 1.7−g₁(−1)+G(−1)=−2.55다. η=0.1에서 다음 점은 각각 0.53,0.955다. 최적점에서 기대 기울기가 0이어도 개별 보폭은 양쪽으로 멀어질 수 있다. 네 추정량을 직접 평균하여 G(x)와 같은지 검산하자.

더 읽기: Johnson과 Zhang의 분산 감소 논문.