arXiv:2601.20571v3 cs.LG

강건하고 비평활 볼록 탈중앙화 학습을 위한 빠르고 효율적인 비동기 고십 알고리즘

Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning

Anna van Elst, Olivier Fercoq, Igor Colin, Stephan Clémençon

제출 2026-01-28

한국어 초록

탈중앙화 비평활 볼록 최적화(non-smooth convex optimization)를 위한 비동기 원쌍대(primal-dual) 방법은 각 노드(node)가 차수(degree)를 $d$라 할 때 $\mathcal{O}(d)$개의 보조 변수를 유지해야 하는 경우가 많습니다. 이러한 차수 의존성은 메모리 요구량을 증가시키며, 특히 밀집 네트워크에서 오래된 정보(stale information)의 영향을 증폭시킬 수 있습니다. 탈중앙화 학습에서 절약형 메모리 관리라는 과제에 착안하여, 본 논문에서는 노드의 차수와 무관하게 노드당 두 개의 변수만 유지하는 비동기 고십(gossip) 기반 원쌍대 알고리즘인 Goal-PD를 제안합니다. Goal-PD가 기저 최적화 문제의 최소화해로 거의 확실히 수렴(almost-sure convergence)함을 규명하고, 목적 함수가 조각별 선형-이차(piecewise linear-quadratic) 형태일 때 선형 수렴함을 증명합니다. 탈중앙화 평균 추정의 경우 쌍별 평균화(pairwise averaging)가 Goal-PD의 특수한 경우임을 보여줌으로써, 제안된 원쌍대 프레임워크와 고전적 고십 알고리즘 간의 직접적인 연결고리를 확립합니다. 중앙값 추정을 비롯한 비평활 목적 함수와 다양한 네트워크 토폴로지에서 합성 및 실제 데이터셋을 대상으로 수행한 실험을 통해, Goal-PD가 설계상 현저히 적은 메모리를 요구하면서도 기존 비동기 베이스라인보다 더 빠르게 수렴함을 보입니다.

원문 초록

Asynchronous primal-dual methods for decentralized non-smooth convex optimization often require each node to maintain $\mathcal{O}(d)$ auxiliary variables, where $d$ is its degree. This dependence on degree increases memory requirements and can amplify the effects of stale information, especially in dense networks. Motivated by the challenge of frugal memory management in decentralized learning, we introduce Goal-PD, an asynchronous gossip-based primal-dual algorithm that maintains only two variables per node, regardless of the node's degree. We establish almost-sure convergence of Goal-PD to a minimizer of the underlying optimization problem, and prove linear convergence when the objective functions are piecewise linear-quadratic. For decentralized mean estimation, we show that pairwise averaging is a special case of Goal-PD, which establishes a direct link between the proposed primal-dual framework and classical gossip. Experiments on synthetic and real datasets over various network topologies, with non-smooth objectives including median estimation, show that Goal-PD converges faster than existing asynchronous baselines while requiring significantly less memory by design.

제출 이력

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

  1. arXiv:2601.20571v3

함께 살펴볼 논문

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

arXiv:2610.05476v2cs.LG공통 태그 Federated Learning, decentralized learning

모집단 확장인가 데이터 희석인가? 탈중앙화 학습에서 국소 토폴로지 진화의 역학

Population Scaling or Data Dilution? Dynamics of Local Topology Evolution in Decentralized Learning

탈중앙화 학습(decentralized learning)의 확장은 클라이언트 수 $N$뿐만 아니라 정보 전파 및 합의 역학도 변화시킵니다. 본 논문에서는 데이터 할당, 토폴로지 의존적 혼합(mixing), 통신 용량이 동시에 변할 수 있으므로 $N$의 증가 효과를 단독으로 이해할 수 없다고 주장합니다. 저자들은 $N\in\{10,50,100,200\}$인 CIFAR-10 환경에서 차수(degree)가 2인 Ring, Static Random 그래프, 그리고 친구의 친구(friend-of-friend) 탐색에 기반한 국소 적응형 토폴로지 과정인 LFHE(Local-First Heuristic Evolution)를 비교하며 이러한 결합된 효과를 연구합니다. Ring은 분석적으로 명확한 실패 모드를 제공합니다. Metropolis 스펙트럼 갭이 $Θ(N^{-2})$로 감소하여, 모집단이 증가함에 따라 모델 불일치의 축소가 점진적으로 느려짐을 의미합니다. 실험 결과, 명목상의 국소 데이터셋 크기를 고정하면 고정된 전체 데이터셋을 더 많은 클라이언트에 분할할 때 관찰되는 외견상의 모집단 불이익이 실질적으로 감소하는 것으로 나타났습니다. 나머지 성능 저하는 통신 구조에 크게 의존합니다. Ring은 높은 불일치 상태에 진입하는 반면, Static Random과 LFHE는 합의 상태에 가깝게 유지됩니다. LFHE의 차수 임계값을 높이면 정확도와 합의가 더욱 향상되지만, 모델 전송 비용이 상당히 증가합니다. 이러한 결과는 탈중앙화 확장이 클라이언트 수 단독이 아닌, 결합된 학습 및 통신 역학에 의해 지배된다는 점을 보여줍니다.

arXiv:2609.27199v1cs.LG공통 태그 Stochastic Optimization, Federated Learning

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.27658v1cs.LG공통 태그 Stochastic Optimization, Federated Learning

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

Private Decentralized Optimization with Noise Reduction and Bias Correction

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

arXiv:2607.14731v1cs.LG공통 태그 Stochastic Optimization, Federated Learning

평활성 상수에는 무엇이 담겨 있는가? 유계 2차 이종성 하 Local SGD의 더 정밀한 수렴률

What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity

Local SGD(연합 평균화(Federated Averaging)로도 알려짐)는 널리 사용되는 분산 최적화(optimization) 알고리즘이다. Local SGD는 실무에서 미니배치 SGD와 같은 대안들보다 종종 더 나은 성능을 보이지만, 이론은 현실적인 데이터 이종성 하에서 로컬 업데이트가 언제·왜 도움이 되는지를 여전히 부분적으로만 설명한다. [Patel et al., 2025]의 최근 연구는 유계 2차 이종성 가정이 강볼록 목적함수에 대한 Local SGD의 효율을 포착한다는 것을 보여 주며, 동일한 원리가 일반 볼록 설정으로 확장된다고 추측한다. 본 논문에서는 유계 2차 이종성 하 일반 볼록 목적함수에 대한 Local SGD의 개선된 수렴 보장을 확립함으로써 이 추측을 증명한다. 또한 이 설정에서 Local SGD에 대한 알려진 최선의 하한을 개선하여, 우리의 상한이 거의 tight함을 보인다. 이러한 결과를 종합하면 Local SGD에 대한 더 날카롭고 세밀한 수렴 이론이 제공된다. 기법의 추가 적용으로, 치환을 사용한 순차 SGD에 대한 하한을 제시하여 2차 이종성이 드문 고곡률(high-curvature) 클라이언트의 영향을 어떻게 포착하는지 보여 준다.

arXiv:2607.08651v1cs.LG공통 태그 Federated Learning, decentralized learning

Secure Decentralized Federated Learning via Gossip and Virtual Voting

분산 연합학습(DFL, Decentralized Federated Learning)은 노드들이 P2P 가십을 통해 모델 업데이트를 교환함으로써 중앙 서버를 제거하지만, 기존 가십 기반 방법들은 출처 최종성(provenance finality)과 비잔틴(Byzantine) 또는 지연(lazy) 참여자에 대한 복원력이 부족한 경우가 많다. 원장(ledger) 보조 연합학습(FL)은 감사 가능성을 향상시키지만, 블록체인, 샤드, 또는 정산 위원회는 DFL의 지역성과 상충되는 전역 조율 비용을 다시 도입할 수 있다. 본 논문은 모델 전파에 사용되는 동일한 가십 이력으로부터 합의를 도출하는 안전한 DFL 프레임워크인 gspDAG-FL을 제안한다. 노드들은 이웃 노드들과만 모델 페이로드를 교환하는 반면, 풀 노드(full node)들은 이벤트 인증서와 수신자 보증 수락 가십 증명을 수집하고, 간결한 토폴로지 방향성 비순환 그래프(DAG)를 재구성하여 해시그래프(Hashgraph) 방식의 가상 투표와 이후 간결한 풀 노드 인증서를 실행한다. 최종성은 동일한 로컬 매개변수 상태가 아닌, 고유한 모델-출처 튜플에 대해 적용된다. 복원력 향상을 위해 gspDAG-FL은 집계 전에 페이로드 검증, 수락 증명 검증, 그리고 프라이빗 시맨틱 감사를 결합한다. 우리는 적대적 환경을 형식화하고, 제어 평면의 안전성과 조건부 활성성(liveness)을 증명하며, 시변 유효 혼합 하에서 인증된 교란 가십에 대한 수렴 보장을 제시한다. 공정한 홀드아웃 검증/감사 데이터와 최대 \(N=100\)의 네트워크를 사용하여 MNIST 분류와 Penn Treebank 언어 모델링에 대한 실험 결과, gspDAG-FL은 혼합 비잔틴 및 지연 참여 환경에서 조율 병목을 줄이고, 처리량을 향상시키며, 높은 유효하지 않은 출처 탐지를 유지하면서 검증 기반 원장 FL에 근접한 학습 품질을 달성함을 보인다.

토론

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