시간적 상관관계의 이점: SGD가 랜덤 워크로부터 k-Juntas를 효율적으로 학습하는 방법

우리는 데이터 내 시간적 상관관계가 특정 희소 학습 문제를 경사 기반(gradient-based) 방법으로 어떻게 효율적으로 학습 가능하게 만드는지 연구합니다. 우리의 초점은 Boolean k-juntas에 맞춰져 있으며, 이는 독립 균일 샘플(independent uniform samples) 하에서 경사 기반 방법의 장벽을 제기하는 것으로 알려진 대표적인 희소 학습 문제입니다. 우리는 이러한 상황이 초입방체(hypercube) 위에서의 게으른 랜덤 워크(lazy random walk)로 샘플이 생성될 때 바뀐다는 것을 보여줍니다. 이 설정에서는 시간적 의존성(temporal dependencies)을 활용하여, 연속된 샘플 간의 목표값과 예측된 증가분(increment)을 비교하는 시간차 손실(temporal-difference loss)을 사용해 훈련된 2층 ReLU 네트워크로 학습할 수 있습니다. 모든 고정된 k에 대해, 결과적인 샘플 복잡도는 주변 차원 d에 본질적으로 선형적입니다. 이와 대조적으로, 표준 볼록 점별 손실(standard convex pointwise losses)을 사용하는 대규모 배치 경사 방법에서는 시간적 상관관계가 동일한 이점을 제공하지 못함을 보여줍니다.