분산 확률적 이중 정규화 비볼록-강오목 미니맥스 문제를 위한 분산 감소 가속 기법
Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems
한국어 초록
본 논문에서는 $m$개의 컴퓨팅 에이전트(agent) 네트워크가 피어 투 피어 통신을 통해 협업하며, 원시 변수(primal variable)와 쌍대 변수(dual variable) 모두에 비매끄러운(nonsmooth) 정규화 항이 존재하는 분산 확률적 비볼록-강오목(NCSC) 미니맥스 문제를 다룹니다. 결합 함수가 기댓값 또는 유한합(finite-sum) 형태이고, 원시 및 쌍대 변수에 각각 적용되는 이중 정규화 항이 볼록 함수인 경우를 고려합니다. 본 연구의 알고리즘 프레임워크는 라그랑주 승수(Lagrangian multiplier)를 도입하여 쌍대 변수에 대한 합의(consensus) 제약 조건을 제거합니다. 이를 분산 감소(VR) 기법과 결합한 제안 방법 VRLM은 반복(iteration)당 단 한 번의 이웃 통신만으로, 대규모 배치 또는 소규모 배치 VR 옵션 모두에서 일반적인 확률적 설정 하에 $\mathcal{O}(κ^3\varepsilon^{-3})$ 표본 복잡도(sample complexity)를 달성합니다. 여기서 $κ$는 문제의 조건수(condition number)이며 $\varepsilon$은 목표 해 정확도입니다. 대규모 배치 VR을 적용하면 추가로 $\mathcal{O}(κ^2\varepsilon^{-2})$의 통신 복잡도를 달성할 수 있습니다. 특수한 유한합 설정 하에서는 대규모 배치 VR을 사용하는 본 방법이 $\mathcal{O}(n + \sqrt{n} κ^2\varepsilon^{-2})$의 표본 복잡도와 $\mathcal{O}(κ^2\varepsilon^{-2})$의 통신 복잡도를 달성할 수 있으며, 여기서 $n$은 유한합의 성분 개수입니다. 모든 복잡도 결과는 본 연구에서 다루는 문제의 특수한 경우를 해결하는 소수의 기존 방법들이 달성한 최고 수준(best-known)의 결과와 일치합니다. 우리가 아는 한, 본 연구는 분산 확률적 설정에서 원시 및 쌍대 변수 모두에 일반적인 볼록 비매끄러운 정규화 항이 적용된 NCSC 미니맥스 문제에 대해 수렴 보장을 제공하는 최초의 연구입니다. 두 가지 머신러닝 문제에 대해 수치 실험을 수행하였으며, 코드는 https://github.com/RPI-OPT/VRLM 에서 다운로드할 수 있습니다.
원문 초록
In this paper, we consider the decentralized, stochastic nonconvex strongly-concave (NCSC) minimax problem with nonsmooth regularization terms on both primal and dual variables, wherein a network of $m$ computing agents collaborate via peer-to-peer communications. We consider when the coupling function is in expectation or finite-sum form and the double regularizers are convex functions, applied separately to the primal and dual variables. Our algorithmic framework introduces a Lagrangian multiplier to eliminate the consensus constraint on the dual variable. Coupling this with variance-reduction (VR) techniques, our proposed method, entitled VRLM, by a single neighbor communication per iteration, is able to achieve an $\mathcal{O}(κ^3\varepsilon^{-3})$ sample complexity under the general stochastic setting, with either a big-batch or small-batch VR option, where $κ$ is the condition number of the problem and $\varepsilon$ is the desired solution accuracy. With a big-batch VR, we can additionally achieve $\mathcal{O}(κ^2\varepsilon^{-2})$ communication complexity. Under the special finite-sum setting, our method with a big-batch VR can achieve an $\mathcal{O}(n + \sqrt{n} κ^2\varepsilon^{-2})$ sample complexity and $\mathcal{O}(κ^2\varepsilon^{-2})$ communication complexity, where $n$ is the number of components in the finite sum. All complexity results match the best-known results achieved by a few existing methods for solving special cases of the problem we consider. To the best of our knowledge, this is the first work which provides convergence guarantees for NCSC minimax problems with general convex nonsmooth regularizers applied to both the primal and dual variables in the decentralized stochastic setting. Numerical experiments are conducted on two machine learning problems. Our code is downloadable from https://github.com/RPI-OPT/VRLM.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Adaptive Variance Reduction across Smoothness and Noise Conditions
분산 감소 정책 그래디언트는 거의 미니맥스-최적이다
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
표준 정책 그래디언트(Policy Gradient, PG) 알고리즘은 몬테카를로 업데이트에 의존하기 때문에 추정 분산이 높다는 문제를 가진다. 오프-정책 분산 감소(off-policy variance reduction)가 이 문제를 완화하지만, 현재로서는 최적의 샘플 복잡도(sample complexity)를 확립하려면 균일하게 유계인(uniformly bounded) 중요도 가중치(importance weights)와 같은 제한적인 가정이나 비현실적인 2차(second-order) 연산이 필요하다. 본 연구에서는 Loopless Variance-Reduced PG(LVR-PG)를 소개한다. 이는 재귀적 업데이트(recursive update)와 방어적 중요도 샘플링(defensive importance sampling)을 결합한 1차(first-order) 추정량들의 한 클래스를 추상화하는 통합 이론적 프레임워크로, PAGE-PG와 STORM-PG와 같은 기존 추정량들을 포함한다. 우리는 일반적인 파라메트릭 정책(parametric policy)에 대해 약한 그래디언트 지배(weak gradient domination) 조건 하에서 이 알고리즘 클래스가 $\tilde{\mathcal{O}}(ε^{-2})$의 라스트 이터레이트(last-iterate) 전역 수렴(global convergence)을 달성함을 증명한다. 우리는 순수하게 1차 업데이트만을 사용하여, 최소한의 가정 하에 그래디언트 전처리기(gradient preconditioner) 없이 이 보장을 확립한다. 최신 하한(lower bound)을 연속적인 파라메트릭 정책(continuous parametric policy)으로 확장함으로써, 우리는 $Ω(ε^{-2})$의 샘플 복잡도 한계를 확립하며, 이는 로그 인자(logarithmic factor)와 호라이즌(horizon) 항을 제외하면 우리의 프레임워크가 미니맥스 최적(minimax-optimal)임을 확인해 준다.
저비용 예측기를 활용한 무작위 모멘텀 전송
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$포인트 높인다.
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)를 갖게 되는 충분 조건을 제시하고, 이 조건을 엄밀하게 만족하는 예시를 함께 제시한다. 실험 결과, 평가한 베이스라인 대비 정확도가 향상됨을 확인하였다.
높은 확률로 확률적 고정점 방정식 풀기
Solving Stochastic Fixed-Point Equations with High Probability
우리는 노름 공간 $(\mathcal{E}, \|\cdot\|)$ 위에서의 확률적 고정점 방정식 $\mathbf{T}(\mathbf{x}) = \mathbf{x}$를 연구한다. 여기서 연산자 $\mathbf{T}$는 비팽창적(nonexpansive) 또는 수축적(contractive)이며, 유계 이차 중심 모멘트를 갖는 비편향 확률적 평가를 통해서만 접근 가능하다. $\varepsilon > 0$, $\delta \in (0, 1)$이 주어졌을 때, 목표는 $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq \varepsilon$을 확률 적어도 $1 - \delta$로 만족하는 $\mathbf{x} \in \mathcal{E}$를 출력하는 것이다. 우리는 이차적으로 평활화 가능한 바나흐(Banach) 공간을 위한 분산 감소(variance-reduced) 점진적 Halpern 방법인 VR-GHAL을 제안한다. 핵심 알고리즘 구성 요소는 오라클 평가의 클리핑된 차이에 기반한 재귀적 확률적 추정기이다: $\tau(\mathbf{x}; \xi)$ 자체를 클리핑하는 대신, 립시츠(Lipschitz) 스케일 $\gamma\|\mathbf{x} - \mathbf{y}\|$에서 확률적 차이를 클리핑한다. 이를 통해 추정기는 알고리즘 궤적을 따라 경로별 립시츠 성질을 유지하면서도, 원래 노름의 유한 이차 모멘트 하에서 마팅게일 집중(martingale concentration)을 허용한다. 우리의 주요 정리는 상시(anytime) 고확률 잔차 한계를 제공한다: 확률 적어도 $1 - \delta$의 단일 사건 위에서, 잔차는 하위 차수 로그 인수를 제외하고 에폭에 걸쳐 거의 기하적으로 감소한다. 유계 분산만을 가정하고 목표 오차 $\varepsilon$ 및 $\mathbf{T}$의 립시츠 상수 $\gamma \in (0, 1]$에 대한 의존성만 표시할 때, 결과적인 오라클 복잡도는 $\min\{\varepsilon^{-5}, (1-\gamma)^{-3}\varepsilon^{-2}\}$이다. 기댓값 립시츠(Lipschitz-in-expectation) 오라클 하에서는 의존성이 대응하는 $\varepsilon^{-3}$ 비팽창적 수렴률($\gamma = 1$의 경우)로 개선되며, 샘플별 비팽창성(samplewise nonexpansiveness) 하에서는 $\varepsilon^{-2}$로 개선된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
Updated to include second author Muhammad Khan who contributed during the rebuttal phase of the submission