랜덤화된 서브스페이스 네스테로프 가속화 경사 하강법

랜덤화된 서브스페이스 (Randomized-subspace) 방법은 저차원 투영 경사 (projected-gradient) 정보만을 사용하여 일차 최적화 (first-order optimization) 비용을 줄이는 방식으로, 이는 포워드 모드 자동 미분 (forward-mode automatic differentiation) 및 통신 제한 환경 (communication-limited settings) 에서 매력적인 특징입니다. 네스테로프 가속화 (Nesterov acceleration) 는 전체 경사 (full-gradient) 및 좌표 기반 방법 (coordinate-based methods) 에 대해 잘 알려져 있지만, 투영 경사 정보만을 사용하여 일반 서브스페이스 스키치 (general subspace sketches) 를 위한 가속화 방법을 얻는 것은 오라클 복잡성 (oracle complexity) 에서 전체 차원 네스테로프 가속화를 개선할 수 있는 기술적으로 비자명한 문제입니다. 우리는 행렬 매끄러움 (matrix smoothness) 및 일반적 스키치 모멘트 가정 (generic sketch moment assumptions) 하에서 매끄러운 볼록 최적화 (smooth convex optimization) 및 매끄러운 강하게 볼록 최적화 (smooth strongly convex optimization) 에 대해 랜덤화된 서브스페이스 네스테로프 가속화 경사 하강법 (randomized-subspace Nesterov accelerated gradient methods) 을 개발했습니다. 핵심 기술적 요소는 행렬 매끄러움에 맞게 조정된 세 가지 시퀀스 형성 (three-sequence formulation) 으로, 이는 전체 차원 경우의 대응되는 고전적인 네스테로프 방법을 복원합니다. 그 결과 이론은 가속화된 오라클 복잡성 보장 (accelerated oracle-complexity guarantees) 을 확립하고 행렬 매끄러움 및 스키치 분포가 복잡성에 어떻게 영향을 미치는지를 명시적으로 보여줍니다. 또한 랜덤화된 서브스페이스 가속화가 전체 차원 네스테로프 가속화보다 오라클 복잡성에서 개선되는 시점을 식별하는 데 있어 스키치 가족 (sketch families) 을 비교할 수 있는 통합된 기초를 제공합니다.