Revisiting Decentralized Online Convex Optimization with Compressed Communication
원문 초록
Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.
요약
통신 압축이 적용된 분산 온라인 볼록 최적화(D-OCO)에서 기존 OGD 기반 알고리즘 대신 처음으로 FTRL 기반 알고리즘 두 가지를 제안하며, FTRL의 이중 변수 업데이트 메커니즘이 Choco-Gossip과 자연스럽게 결합됨을 보인다. 완전 정보 설정에서는 기존 후회 한계(regret bound)를 달성하고, 밴딧(bandit) 설정에서는 볼록 및 강볼록 함수 모두에서 후회 한계와 통신 비용을 동시에 개선한다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.01665v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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)을 구분한다.
노이즈 감소와 바이어스 보정을 통한 프라이빗 분산 최적화
Private Decentralized Optimization with Noise Reduction and Bias Correction
프라이빗 분산 학습은 이질적인 데이터 환경에서 샘플링 노이즈, 프라이버시 노이즈, 그리고 분산 바이어스의 영향을 받는다. 본 논문은 Private Recursive Decentralized Optimization(PRDO)을 제안한다. PRDO는 동일 배치 그래디언트 차이를 이용한 재귀적 추정(recursive estimation)으로 샘플링 노이즈와 프라이버시 노이즈에 의한 추정 오차를 줄이고, Exact Diffusion 구성 요소로 데이터 이질성에서 비롯되는 분산 바이어스를 보정한다. 본 분석은 노드 간 데이터 이질성이 균일하게 유계라는 가정 없이 비볼록(nonconvex) 수렴 바운드를 도출한다. 또한 재귀적 그래디언트 차이가 프라이빗 Exact Diffusion보다 엄밀하게 더 낮은 쿼리 민감도(query sensitivity)를 갖게 되는 충분 조건을 제시하고, 이 조건을 엄밀하게 만족하는 예시를 함께 제시한다. 실험 결과, 평가한 베이스라인 대비 정확도가 향상됨을 확인하였다.
평활성 상수에는 무엇이 담겨 있는가? 유계 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) 클라이언트의 영향을 어떻게 포착하는지 보여 준다.
데이터 기반 블록 교체 스케줄링
Data Driven Block Replacement Scheduling
우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.
Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem
낮은 자기상관 이진 수열 문제(LABS)는 통신, 신호 처리, 위성 항법 분야에서 중요한 응용을 갖는 어려운 조합 최적화 과제이다. 본 논문은 LABS 탐색 공간의 제한 클래스에 걸쳐 계산 노력을 적응적으로 배분하기 위해 Thompson 샘플링과 병렬 자기회피 보행(self-avoiding walk)을 결합한 하이브리드 탐색 프레임워크를 제안한다. 파티션을 다중 팔 밴딧(multi-armed bandit) 설정의 팔(arm)로 모델링함으로써, 제안된 방법은 덜 샘플링된 영역의 탐험(exploration)을 유지하면서도 경험적으로 더 높은 성능 지수(merit factor)를 산출하는 파티션 쪽으로 탐색 자원을 동적으로 전환한다. 이 접근법은 GPU 병렬 실행, 공유 사후 업데이트, 효율적인 이웃 평가, 그리고 사이클 방지를 위한 블룸 필터(Bloom filter)를 통해 추가로 가속된다. 또한 제약된 분할 비대칭 공간(partitioned skew-symmetric space)을 먼저 탐색한 후 비제약 공간에서 최적 후보를 정제하는 2단계 최적화 전략을 사용한다. 긴 이진 수열에 대한 실험 결과, 제안된 방법은 $450 \le L \le 527$ 범위의 35개 수열 길이와 $L=573$에 대해 이전에 알려진 최선의 결과를 개선하였다. 특히 $L=451$에서 성능 지수 8.0을 초과하는 새로운 최장 수열을 보고한다. 결과는 또한 Thompson 샘플링이 더 나은 관측 성능을 보이는 파티션을 효과적으로 우선시함을 보여주며, LABS 최적화에서 온라인 데이터 기반 자원 배분의 가치를 확인한다. 전반적으로 제안된 프레임워크는 고성능 성능 지수 최대화를 위한 확장 가능하고 효과적인 전략을 제공한다.
Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.