확률적 모멘텀 방법론의 연산 효율성 및 직렬 실행 시간 간의 트레이드오프

Heavy Ball (HB), Nesterov momentum, 그리고 Accelerated SGD (ASGD) [Kidambi et al., 2018]의 변형들과 같은 확률적 모멘텀 방법론 (Stochastic momentum methods)은 현대적인 학습 과정에서 널리 사용되지만, 이들의 확률적 이점은 두 가지 별개의 양에 따라 달라집니다: 목표 정확도에 도달하는 데 필요한 반복 횟수인 직렬 실행 시간 (serial runtime), 그리고 전체 그래디언트 쿼리(gradient-query) 또는 FLOP 비용의 역수인 연산 효율성 (compute efficiency, CE)입니다. 배치 크기 (batch size)가 커질 때 CE를 해치지 않으면서 직렬 실행 시간을 줄일 수 있는 경우는 오직 수축 간격 (contraction gap)이 배치 크기에 따라 선형적으로 증가할 때뿐입니다. 본 연구에서는 가우시안 공변량 (Gaussian covariates)을 가진 일관된 선형 회귀 (consistent linear regression)에 대해 확률적 HB 및 ASGD를 연구하며, 이들의 배치 크기 트레이드오프에 대한 유한 차원, 이산 시간 하한 (finite-dimensional, discrete-time lower bounds)을 증명합니다. 우리의 첫 번째 결과는 HB가 임의의 스펙트럼 (spectra)에 대해 SGD보다 CE 프런티어 (CE frontier)를 개선하지 못한다는 것을 보여줍니다. 오히려 HB는 더 넓은 배치 크기 범위에서 SGD 수준의 CE를 유지하며, HB가 결정론적 가속 스케일 (deterministic accelerated scale)에 도달할 때까지 더 큰 배치를 통해 직렬 실행 시간을 줄일 수 있게 합니다. 이 범위는 SGD 임계 배치 크기 (critical batch size)보다 $\sqrtκ$ 배만큼 더 클 수 있습니다. ASGD의 경우, 상황은 스펙트럼에 더 의존적입니다. 급격히 감소하는 멱법칙 스펙트럼 (power-law spectra)의 경우, ASGD는 작은 배치에서 HB/SGD보다 CE를 개선하지만, 배치 크기가 커짐에 따라 이러한 CE 이점을 개선된 직렬 실행 시간과 맞바꿉니다 (trade). 합성 선형 회귀 실험을 통해 이러한 질적 영역들을 검증하였으며, 여기에는 천천히 감소하는 스펙트럼에 대한 ASGD와 HB의 거의 중첩되는 양상과 급격히 감소하는 스펙트럼에 대해 예측된 CE--직렬 트레이드오프가 포함됩니다.