arXiv:2606.07496v1 cs.LG

강하게 볼록한 최적화를 위한 가속된 분산 확률적 경사하강법

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Ming Sun, Kun Yuan

제출 2026-06-05

한국어 초록

분산 확률적 최적화(decentralized stochastic optimization)는 네트워크 상에서의 대규모 학습을 위한 기본 패러다임으로, 에이전트가 이웃과만 통신하며 중앙 코디네이터가 필요하지 않습니다. 강하게 볼록한 문제의 경우, 통신 효율성은 주로 조건수(condition number) \(κ=L/μ\)와 네트워크 스펙트럼 갭(spectral gap) \(1-β\)에 의해 결정됩니다. 결정론적 분산 방법은 가속된 \(\sqrtκ\) 및 \(1/\sqrt{1-β}\) 의존성을 동시에 달성할 수 있지만, 기존의 확률적 방법 중에는 두 가지 개선을 동시에 달성하는 것이 없습니다. 본 논문에서는 Nesterov형 프리멀-듀얼(primal-dual) 외삽과 다중 라운드 빠른 고시프(gossip) 평균화를 결합한 분산 확률적 알고리즘인 \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD)를 제안합니다. 핵심 아이디어는 고시프 깊이를 미니배치(mini-batch) 크기와 결합하여, 추가적인 통신 라운드가 합의(consensus) 정확도를 높이고 그래디언트(gradient) 분산을 줄이도록 하는 것입니다. 우리는 MG-ADSGD가 다음의 통신 복잡도 \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] 를 달성함을 보여줍니다. 여기서 \(ε\)는 목표 정확도, \(n\)은 노드 수, \(σ^2\)는 그래디언트 분산을 나타냅니다. 우리의 아는 한, 이 바운드는 $ε$과 무관한 로그 인자를 제외하고, 분산 확률적 강하게 볼록한 최적화에 대해 현재 가능한 최고의 통신 복잡도를 제공합니다.

원문 초록

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number \(κ=L/μ\) and the network spectral gap \(1-β\). Although deterministic decentralized methods can simultaneously achieve accelerated \(\sqrtκ\) and \(1/\sqrt{1-β}\) dependences, no existing stochastic method attains both improvements at once. In this paper, we propose \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] where \(ε\) denotes the target accuracy, \(n\) is the number of nodes, and \(σ^2\) is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of $ε$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.07496v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.35297v3cs.LG공통 태그 Computational Efficiency, Stochastic Optimization

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

arXiv:2609.27199v1cs.LG공통 태그 Stochastic Optimization, decentralized optimization

ZO-COSMO: 분산 제로차 최적화를 위한 인덱스 없는 원홉(one-hop) 혼합

ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization

분산 제로차 학습에서 희소 통신은 호환 가능한 피어 상태 좌표(peer-state coordinates)를 요구한다. 우리는 이 원홉(one-hop) 조건을 특성화하고, 활성 링크당 $q$개 값을 사용하는 평균 보존 마스크 합의(average-preserving masked consensus)와 이중 쿼리 추정(two-query estimation)을 결합한 \textsf{ZO-COSMO}를 제안한다. 전역 지원(global supports)은 전 이웃 혼합(all-neighbor mixing)에 사용되며, 매칭 업데이트(matching updates)는 각 쌍 내에서만 합의를 요구한다. 매칭 클래스 내에서 날카로운 스칼라당 수축(contraction-per-scalar) 상계를 유도하고, 핵심 및 희소-모멘텀(sparse-momentum) 업데이트에 대한 수렴 보장을 제공한다. 고정된 매칭에서 정확한 모멘트 항등식(moment identities)은 공유 방향이 그래디언트 이질성(gradient-heterogeneity) 상쇄를 어떻게 보존하고 추정 오차와 불일치(disagreement)를 재분배하는지를 특성화한다. 메커니즘 실험은 불균등 곡률, 노이즈, 희소 모멘텀을 다룬다. 추가 실험은 $64$개의 합성 에이전트와 8개의 논리적 Qwen LoRA 워커를 포함한다. 동일한 페이로드 예산에서 Qwen2-7B QNLI는 explicit-index Rand-$k$ 대비 $3.65$ 정확도 포인트를 얻으며, 8-워커 완전 그래프와 링 그래프에서 edge-local 업데이트는 전 이웃 혼합 대비 각각 $3.42$ 및 $2.53$ 포인트를 얻는다. 매칭-first-step 소거(ablation)는 $3.92$ 포인트의 모멘텀 이득을 보여준다. 시드 인식(seed-aware) 및 동일-매칭(same-matching) 대조는 인코딩, 스케줄링, 쿼리 상관(query correlation)을 구분한다.

arXiv:2609.27577v1cs.LG공통 태그 Computational Efficiency, Stochastic Optimization

VCMM: 멀티모달 학습을 위한 분산 보정 모멘텀

VCMM: Variance-Calibrated Momentum for Multimodal Learning

멀티모달 공동 학습(multimodal joint training)은 지배적인 모달리티가 다른 모달리티의 최적화를 억제하는 모달리티 불균형 문제를 자주 겪습니다. 기존 방법들은 주로 그래디언트의 크기나 방향을 조절하거나, 최적화 목적 함수를 수정하거나, 학습 전략을 조정하여 모달리티 학습의 균형을 맞추며, 대부분의 개입은 현재의 업데이트에 초점을 맞춥니다. 그러나 널리 사용되는 모멘텀 기반 옵티마이저와 결합될 경우, 업데이트에는 이전 그래디언트로부터 누적된 정보도 포함되며, 이는 현재 단계의 조절만으로는 명시적으로 해결되지 않습니다. 이러한 문제를 해결하기 위해, 모달리티별 그래디언트 동역학에 맞춰 그래디언트 메모리를 적응시키는 분산 보정 모멘텀(Variance-Calibrated MomentuM, VCMM)을 제안합니다. 구체적으로, VCMM은 미니배치 노이즈와 시간적 드리프트(temporal drift)를 온라인으로 추정하고, 칼만(Kalman)에서 영감을 얻은 제어기를 통해 이들의 상대적 강도를 활용하여 모달리티별 모멘텀을 결정합니다. 나아가 모달리티 간 제어 신호를 중앙화하고 시간에 따라 변하는 1차 모멘트에 대한 정확한 바이어스 수정을 적용함으로써, 추가적인 네트워크 패스나 명시적인 학습률 스케일링 없이도 적응형 그래디언트 메모리를 구현합니다. 네 가지 멀티모달 벤치마크에 대한 실험은 적은 학습 오버헤드로 일관된 성능 향상을 입증합니다.

arXiv:2609.27581v1cs.LG공통 태그 Computational Efficiency, Stochastic Optimization

Step Law는 소규모 언어 모델에도 전이되는가? 59M 파라미터 미만에서의 실증적 재보정

Does Step Law Transfer to Small-Scale Language Models? An Empirical Recalibration Below 59M Parameters

Step Law는 언어 모델 사전학습 시 최적 피크 학습률 η*와 배치 크기 B*에 대한 멱법칙(power-law) 공식을 제공한다. 원 저자들은 59M~1B 파라미터 모델에서 이를 보정했으며, N < 59M인 소규모 모델 영역은 실증적으로 검증한 적이 없다. 이 영역은 단일 GPU 학습, 해석 가능성 연구, 교육용 실험, 메모리·비용상 더 큰 모델을 쓰기 어려운 환경에서 중요하다. 우리는 Step Law가 소규모 언어 모델에도 전이되는지 검증한다. 세 가지 결과를 가정한다. H1: 원래 계수를 그대로 쓸 수 있다. H2: 멱법칙 형태는 유지되나 계수가 다르다. H3: 이 영역에서는 멱법칙이 최적점을 설명하지 못한다. 모든 실험은 2048 토큰 BPE 어휘, AdamW, warmup-cosine 스케줄을 사용하는 단일 nanoGPT/TinyStories 파이프라인에서 수행했다. 각 (N, D) 셀의 최적점은 평활화된 학습 손실에 대해 log-log 좌표에서 국소 이차 근사를 통해 손실 표면 L(η, B)에서 추출했다. 최종 데이터셋은 서로 다른 (N, D) 셀 29개와 분석에 사용 가능한 run 935개를 포함한다. 주 재적합은 작업 구간 4 <= D/N <= 600에서 25개 셀(815 runs)을 사용한다. 풀링 데이터에서는 H2를 채택한다. 함수 형태는 유지되나 계수는 원 논문과 다르다. η*(N, D) = 0.0985 N^(-0.508) D^(0.238) (R^2 = 0.834)와 B*(D) = 3.6 × 10^(-4) D^(0.931) (R^2 = 0.950)를 얻었다. Step Law의 구조적 주장인 B*의 N 비의존성은 재현된다(p = 0.87). 다만 B*가 D에 따라 증가하는 기울기는 원 논문의 거의 2배다. Step Law를 직접 전이하면 최적 학습률을 체계적으로 과대 추정한다. η_SL / η*의 중앙값 비는 약 4.0배이며, 범위는 2.4배에서 6.6배이다.

arXiv:2609.27658v1cs.LG공통 태그 Stochastic Optimization, decentralized optimization

노이즈 감소와 바이어스 보정을 통한 프라이빗 분산 최적화

Private Decentralized Optimization with Noise Reduction and Bias Correction

프라이빗 분산 학습은 이질적인 데이터 환경에서 샘플링 노이즈, 프라이버시 노이즈, 그리고 분산 바이어스의 영향을 받는다. 본 논문은 Private Recursive Decentralized Optimization(PRDO)을 제안한다. PRDO는 동일 배치 그래디언트 차이를 이용한 재귀적 추정(recursive estimation)으로 샘플링 노이즈와 프라이버시 노이즈에 의한 추정 오차를 줄이고, Exact Diffusion 구성 요소로 데이터 이질성에서 비롯되는 분산 바이어스를 보정한다. 본 분석은 노드 간 데이터 이질성이 균일하게 유계라는 가정 없이 비볼록(nonconvex) 수렴 바운드를 도출한다. 또한 재귀적 그래디언트 차이가 프라이빗 Exact Diffusion보다 엄밀하게 더 낮은 쿼리 민감도(query sensitivity)를 갖게 되는 충분 조건을 제시하고, 이 조건을 엄밀하게 만족하는 예시를 함께 제시한다. 실험 결과, 평가한 베이스라인 대비 정확도가 향상됨을 확인하였다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.