Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods
한국어 초록
Heavy ball (HB), Nesterov 모멘텀, Accelerated SGD (ASGD) [Kidambi et al., 2018]의 변형과 같은 확률적 모멘텀 방법들은 현대 학습에서 널리 사용되지만, 이들의 확률적 이점은 두 가지 별개의 양, 즉 목표 정확도에 도달하는 데 필요한 반복 횟수인 직렬 런타임과 전체 그래디언트 쿼리 또는 FLOP 비용의 역수인 계산 효율성(CE)에 의존합니다. 더 큰 배치는 수축 간극이 배치 크기에 따라 선형적으로 증가할 때에만 CE를 저해하지 않으면서 직렬 런타임을 줄입니다. 우리는 가우시안 공변량을 갖는 일치 선형 회귀에 대해 확률적 HB와 ASGD를 연구하고, 그들의 배치 크기 트레이드오프에 대한 유한 차원 이산 시간 하한을 증명합니다. 첫 번째 결과는 HB가 임의의 스펙트럼에 대해 SGD 대비 CE 프론티어를 개선하지 않음을 보여줍니다. 오히려 HB는 더 큰 배치 크기 윈도우에 걸쳐 SGD 수준의 CE를 유지하여, HB가 결정론적 가속 규모에 도달할 때까지 더 큰 배치가 직렬 런타임을 줄일 수 있도록 합니다. 이 윈도우는 SGD 임계 배치 크기보다 $\sqrtκ$배 더 클 수 있습니다. ASGD의 경우 그 양상은 스펙트럼에 더 의존적입니다. 급격히 감소하는 멱법칙 스펙트럼의 경우, ASGD는 HB/SGD 대비 소배치 CE를 개선하지만, 배치 크기가 증가함에 따라 이 CE 이점을 개선된 직렬 런타임과 교환합니다. 합성 선형 회귀 실험은 천천히 감소하는 스펙트럼에 대한 ASGD와 HB의 거의 겹침과 급격히 감소하는 스펙트럼에 대한 예측된 CE-직렬 트레이드오프를 포함하여 이러한 정성적 체제를 검증합니다.
원문 초록
Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor $\sqrtκ$ larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.19179v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
반복 데이터 사전학습 스케일링: 배치 크기, 정규화 및 GPU-시간 트레이드오프
Scaling Repeated-Data Pretraining: Batch Size, Regularization, and GPU-Time Tradeoffs
본 연구에서는 연산량은 풍부하지만 고유한 학습(training) 데이터가 유한하여 동일한 데이터에 대한 반복 학습이 필요한 환경에서의 사전학습(pre-training)을 다룹니다. 먼저 무한 연산량 사전학습(Kim et al. 2026)을 재검토하여, 그 프론티어가 기존에 고정되었거나 개별적으로만 연구되었던 선택 사항들에 결정적으로 의존함을 보입니다. 특히 에포크(epoch) 수와 함께 배치(batch) 크기를 최적화하면 검증 손실(validation loss)과 배치 크기 사이에 U자형 관계가 나타나 일반적인 사전학습보다 더 작은 배치를 선호하게 됨을 밝히며, 이는 소배치 그래디언트(gradient) 노이즈가 암묵적 정규화(implicit regularization)를 제공하기 때문인 것으로 보입니다. 나아가 기존에 단일 패스 가정 하에서 최적화되었던 학습 레시피를 조정할 수 있음을 확인했습니다. 예를 들어 에포크마다 문서를 새로운 시퀀스로 재패킹하는 것, 가중치 공유(weight tying), 그리고 양의 임베딩 가중치 감쇠(positive embedding weight decay) 등이 있습니다. 이후 무한 연산량 가정을 완화합니다. 특히 일반적인 경우보다 작은 배치 크기는 지나치게 긴 순차적 학습 시간을 요구할 수 있으므로, GPU와 시간을 별개의 자원으로 다루어야 할 필요성이 발생합니다. 마감 기한이 촉박할수록 더 큰 배치가 유리하며, 지연 시간 중심의 병렬 처리를 통해 추가 GPU를 투입하여 학습 시간을 단축할 수 있습니다. 그럼에도 불구하고 고정된 시간 예산 내에서도 더 적은 수의 GPU와 작은 배치를 사용하는 것이 더 많은 GPU와 큰 배치를 사용하는 것보다 더 낮은 검증 손실을 달성할 수 있으며, 이는 마감 기한 내에서 GPU 활용도를 극대화하기 위해 데이터 병렬 처리를 늘리는 일반적인 관행에 도전합니다. 종합적으로 본 연구 결과는 반복 데이터 학습에서 충분히 탐구되지 않았던 요인들을 식별하고, 단일 패스 사전학습 대비 학습 레시피와 자원 할당이 어떻게 변화해야 하는지에 대한 구체적인 지침을 제공합니다.
BLOKS: 스케치된 블록 전처리를 통한 커널 솔버의 스케일링
BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
커널 리지 회귀(Kernel Ridge Regression, KRR)는 비매개변수적 학습(nonparametric learning)을 위한 이론적으로 타당한 알고리즘이며, 심층 학습(deep learning)의 특성을 연구하는 데에도 자주 사용된다. 그러나 정확한(exact) KRR 수식은 대규모 데이터셋(dataset)에 적용할 수 없을 정도의 시간 및 메모리 비용을 발생시키며, 이는 근사 솔버(approximate solver) 개발의 동기가 되었다. 이러한 알고리즘들은 (i) 직접적인 해법의 계산 부담을 피하기 위한 반복적 방법(iterative method), (ii) 문제 크기를 줄이기 위한 스케칭(sketching) 또는 배치화(batching), (iii) 수렴(convergence)을 가속화하기 위한 전처리(preconditioning)에 의존한다. 빠른 수렴을 위해 필수적이지만, 전처리는 메모리 비용을 발생시키며, 이는 모델(model)의 자유 매개변수 수를 줄임으로써 관리할 수 있으나 그 대가로 표현력, 나아가 정확도가 저하될 수 있다. 이러한 문제를 해결하기 위해, 우리는 블록 자코비(Jacobi) 근사와 스케칭을 결합한 새로운 프리컨디셔너(preconditioner)를 중심으로 구축된, Nyström 방식으로 스케치된 KRR을 위한 컨주게이트 그래디언트(Conjugate Gradient) 기반 솔버인 BLOKS를 제안한다. BLOKS의 프리컨디셔너는 데이터셋 크기와 매개변수 수 모두와 무관한 메모리 비용을 가지므로, 대규모 모델로의 스케일링(scaling)이 가능하다. 우리는 메모리 효율적이고 GPU로 가속화된 구현을 제공하며, BLOKS가 우수한 시간/메모리 복잡도를 유지하면서도 뛰어난 정확도를 달성함을 보인다. 실제로, 커널 솔버를 벤치마킹(benchmark)하는 데 사용되는 표준 대규모 데이터셋에서 BLOKS는 최신(state-of-the-art) 기법들과 비교할 만하거나 그보다 더 나은 성능을 달성한다.
저비용 예측기를 활용한 무작위 모멘텀 전송
Randomized Momentum Transport with Cheap Predictors
STORM 및 2차 모멘텀(second-order momentum)과 같은 모멘텀(momentum) 방법들은 모멘텀에 전송 보정(transport correction)을 추가하여 그래디언트(gradient)를 추적하며, 이는 반복(iteration)마다 추가적인 오라클(oracle) 호출을 필요로 한다. 본 논문은 확률 $q$로 보정을 평가하고 그렇지 않은 경우 저비용 예측(cheap prediction)을 사용하는 무작위 모멘텀 전송(randomized momentum transport)을 소개하며, 조건부 평균을 보존하는 중요도 가중(importance weighting)을 사용하고 분산에 예측 손실(loss)의 $(q^{-1}-1)$배를 추가한다. 전송 바이어스(bias), 2차 모멘트, 잔차 제어 가정 하에서, 정규화(normalized), 사인(sign), 정확한 스펙트럴(exact spectral, Muon) 방향을 포함한 선형 최소화 오라클(linear minimization oracle, LMO) 업데이트는 단일 그래디언트 초기화(initialization)를 사용하여 고정된 각 $q>0$에 대해 $O(T^{-1/3})$ 정상성(stationarity) 바운드를 유지한다. 정규화되지 않은(unnormalized) STORM의 경우, 그래디언트 차이 노이즈 모듈러스가 평활성 상수를 초과하는 경우에만 (그리고 오직 그 경우에만) 일부 $q<1$이 충분 그래디언트 예산의 선도 계수를 최대 약 $10\%$까지 낮춘다. 온라인 대각 예측기는 후회-수렴(regret-to-convergence) 보장을 허용한다. 오라클 비용이 거의 동일한 조건에서, 보정값의 4분의 1만 조회하는 것은 MNIST1D에서 최종 학습(training) 손실(loss)을 $18$에서 $43\%$까지 낮추고, CIFAR-10에서 헤시안(Hessian)-벡터 전송의 테스트 정확도를 $1.5$포인트 높인다.
LionMuon: 효율적인 학습을 위한 스펙트럼 및 부호 하강 교차 기법
LionMuon: Alternating Spectral and Sign Descent for Efficient Training
언어 모델 사전학습에는 막대한 양의 연산량이 소모되며, 적절한 옵티마이저를 사용하면 이를 상당 부분 절감할 수 있습니다. Muon의 스펙트럼 스텝은 부호(sign) 스텝보다 더 강력한 방향을 제공하지만 연산 비용이 큽니다. 매 스텝마다 전체 행렬에 대해 뉴턴-슐츠 반복(Newton-Schulz iterations)을 수행하며, 분산 학습 환경에서는 추가적인 올리듀스(all-reduce)가 발생합니다. 반면 Lion 및 Signum과 같은 부호 스텝은 비용이 저렴하며 각 디바이스에 국소적으로 유지됩니다. 본 논문에서는 $P$ 반복마다 한 번의 Muon 스텝을 수행하고 그 사이에는 Lion 스텝을 수행하며, 두 방식이 단일 듀얼 EMA 모멘텀 버퍼를 공유하는 LionMuon을 제안합니다. Muon의 연산 및 통신 비용은 $P$ 스텝마다 한 번만 발생하며, 옵티마이저 상태 메모리는 AdamW의 절반 수준입니다. 단일 EMA 변형인 SignMuon만으로도 이미 Muon 대비 성능 향상을 보입니다. 저자들은 주기 $P$가 Muon과 Lion의 매끄러움(smoothness) 및 노이즈 상수를 보간하며 LionMuon이 두 방법보다 더 빠른 조건을 제시하는 꼬리가 두꺼운 노이즈(heavy-tailed noise) 환경에서의 복잡도 한계를 증명합니다. FineWeb으로 학습된 124M 및 355M 모델에서 $P=2$ 및 $P=5$인 LionMuon은 동일한 토큰 수에서 Muon, AdamW, Lion, Signum보다 더 낮은 손실을 달성합니다. 4개 GPU 데이터 병렬 학습 환경의 PCIe 상에서 LionMuon은 Muon의 최종 손실에 도달하면서도 소요 시간(wall-clock)을 3분의 1 줄였으며, 정확한 그래디언트를 유지하면서도 노출되는 통신량 증가 없이 통신 효율적인 Muon 변형인 Dion 및 MuonBP보다 더 우수한 손실 성능을 보입니다. 코드: https://github.com/brain-lab-research/lion-muon
희소 가우시안 프로세스 회귀에서의 기저 함수 선택
On Basis Function Selection for Sparse Gaussian Process Regression
희소 가우시안 프로세스는 입력 공간 상의 고정 기저 $\{\phi_j\}$로의 적절한 전개로 커널을 대체함으로써 $O(N)$ 추론을 달성한다. 계산 예산 $M \ll N$이 주어지면, 실무자들은 관례적으로 기저를 처음 $M$개 항으로 잘라(truncate) 사용한다. 그러나 형식적 프레임워크상 데이터에 실제로 중요한 $M$개의 기저 함수만 선택하는 것을 막을 수는 없다. 이렇게 하면 신호가 없는 기저 함수에 예산을 쓰는 것을 피할 수 있지만, 후보를 순위 매기기 위한 기준이 필요하다. 우리는 기저 함수 선택 문제에 대한 정보 이론적 관점에서 도출한 세 가지 기준을 제안한다. 각 기준은 선택 시점의 서로 다른 지식 상태에 대응한다: 무-데이터(no-data) 상태, 무-사전(no-prior) 상태, 그리고 그 중간(in-between) 상태. 그런 다음 세 가지 기저 계열—Hilbert 공간 가우시안 프로세스(HSGP), 변분 푸리에 특징(VFF), 변분 inducing 구면 조화(VISH)—에 대해 여섯 개의 UCI 회귀 벤치마크에서 절단(truncation) 대비 선택(selection) 전략의 성능을 연구한다. 우리는 무-데이터 기준이 안전한 기본값이며, HSGP, VFF, VISH에 대해 절단과 동등하거나 더 나은 성능을 보이고, VISH에서는 상당한 이득을, 해당 기저 계열에 대해 최근 개발된 선택 휴리스틱 대비 개선을 보인다고 관찰한다. 데이터를 고려한 무-사전 및 중간 기준은 세 계열 중 실무에서 가장 널리 쓰이는 HSGP에 대해 절단 대비 상당한 이득을 제공한다.
잔차 기반 적응형 GMsFEM을 위한 가우시안 프로세스 대리 지표
Gaussian-process surrogate indicators for residual-based adaptive GMsFEM
고대비(high-contrast) 타원형 문제에 대한 잔차 기반 적응형 GMsFEM은 모든 coarse 이웃에서 국소 가중 $H^{-1}$ 지표를 반복적으로 평가하므로, 반복 쿼리(repeated-query) 설정에서 지표 평가가 반복되는 비용이 된다. D\"orfler marking에 사용되는 지표 점수에 대해 비침투적(non-intrusive) 가우시안 프로세스(GP) 대리 모형을 도입한다. 운영 예측량은 GP 사후 평균이며, 명시된 규약 하에서 커널 릿지 회귀(KRR) 추정량과 대수적으로 동등하다; 다중스케일 해법, 국소 스펙트럼 구성, 또는 기저 enrichment를 바꾸지 않고 압축된 국소 해와 스펙트럼 특징을 사용한다. 비균일 perturbed-marking 결과는 점별 점수 오차가 대리 모형이 선택한 이웃이 포착하는 정확한 지표 질량(indicator mass)에 미치는 영향을 정량화하고, 조건부 bounded-discrepancy KRR 경로는 이러한 점수 경계에 대한 충분한 가정을 밝힌다. 통제된 held-out in-distribution 테스트에서, 대리 모형이 안내하는 방법은 고전적 $H^{-1}$-잔차 오프라인 적응성과 비교 가능한 오차 대 자유도(DoF) 추세를 보이며, 오프라인 데이터 생성 및 GP 학습을 제외하면 온라인 지표 구성 요소 평가가 2.0–2.1배 빠르다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.