arXiv:2507.12091v2 math.OC

부호 기반 모멘텀 방법론을 위한 개선된 수렴 보장

Better Convergence Guarantees for Sign-Based Momentum Methods

Wei Jiang, Dingzhi Yu, Sifan Yang, Wenhao Yang, Zechao Li, Lijun Zhang

제출 2025-07-16

한국어 초록

본 논문은 모멘텀(momentum) 업데이트를 사용하는 부호 기반 방법론(sign-based methods)에 대한 개선된 분석을 제시합니다. 기존의 부호 기반 방법론은 분리 가능한 매끄러움(separable smoothness) 가정 하에서 $\mathcal{O}(T^{-1/4})$의 수렴 속도를 달성하지만, 일반적으로 큰 배치 크기를 필요로 하거나 단봉형 대칭 확률적 노이즈(unimodal symmetric stochastic noise)를 가정합니다. 이러한 한계를 해결하기 위해, 본 연구에서는 모멘텀을 적용한 signSGD가 추가적인 가정 없이 일정한 배치 크기를 사용하여 동일한 수렴 속도를 달성할 수 있음을 입증합니다. 또한 $l_2$-매끄러움 조건 하에서의 수렴 속도를 규명하여 문제의 차원 $d$에 대해 기존 연구 결과보다 $\mathcal{O}(d^{1/2})$만큼 향상된 결과를 제시합니다. 나아가 분산 환경에서의 부호 기반 방법론을 탐구하여, 제안된 방법이 각각 기존 결과인 $\mathcal{O}\left( dT^{-1/4} + dn^{-1/2} \right)$ 및 $\mathcal{O}\left( d^{3/8}T^{-1/8} \right)$을 능가하는 $\mathcal{O}\left( d^{1/2}T^{-1/2} + dn^{-1/2} \right)$ 및 $\mathcal{O}\left(d^{1/4}T^{-1/4}\right)$의 수렴 속도를 제공함을 보입니다. 수치 실험을 통해서도 제안된 방법들의 효과를 검증합니다.

원문 초록

This paper presents an improved analysis for sign-based methods with momentum updates. Traditional sign-based methods obtain a convergence rate of $\mathcal{O}(T^{-1/4})$ under the separable smoothness assumption, but they typically require large batch sizes or assume unimodal symmetric stochastic noise. To address these limitations, we demonstrate that signSGD with momentum can achieve the same convergence rate using constant batch sizes without additional assumptions. We also establish a convergence rate under the $l_2$-smoothness condition, improving upon the result of prior work by a factor of $\mathcal{O}(d^{1/2})$, where $d$ is the problem dimension. Furthermore, we explore sign-based methods in distributed settings and show that the proposed methods yield convergence rates of $\mathcal{O}\left( d^{1/2}T^{-1/2} + dn^{-1/2} \right)$ and $\mathcal{O}\left(d^{1/4}T^{-1/4}\right)$, which outperform the previous results of $\mathcal{O}\left( dT^{-1/4} + dn^{-1/2} \right)$ and $\mathcal{O}\left( d^{3/8}T^{-1/8} \right)$, respectively. Numerical experiments also validate the effectiveness of the proposed methods.

제출 이력

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

  1. arXiv:2507.12091v2

함께 살펴볼 논문

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

arXiv:2607.08104v2cs.LG공통 태그 Stochastic Optimization, convergence analysis

바닐라 SGD와 모멘텀은 헤비테일 노이즈에서도 수렴한다: 그래디언트 클리핑 또는 정규화 없는 수렴 분석

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

확률적 경사하강법(SGD)은 현대 최적화의 핵심 기법이다. 헤비테일 노이즈 환경에서의 성능은 흔히 그래디언트 클리핑이나 정규화와 같은 특수한 변형을 통해 다루어지지만, 본 연구는 보다 근본적인 질문을 탐구한다: 바닐라 SGD, 특히 모멘텀을 적용한 경우, 헤비테일 노이즈가 존재할 때 어떻게 동작하는가? 본 논문에서는 바닐라 SGD의 기존 수렴 결과를 개선하고, 더 나아가 어떠한 그래디언트 제어 메커니즘도 사용하지 않고 강볼록(strongly convex), 볼록(convex), 비볼록(nonconvex) 목적함수에 대한 모멘텀을 갖춘 바닐라 SGD의 최초의 포괄적인 수렴 분석을 제공한다. 분석 결과, 도출된 수렴 속도는 클리핑 또는 정규화 변형 SGD가 달성하는 최적 속도보다 열등함을 보이며, 이를 통해 헤비테일 노이즈 환경에서 바닐라 방법이 갖는 본질적인 한계를 밝힌다. 이론적 결과는 합성 함수에 대한 실험을 통해 뒷받침된다.

arXiv:2607.22211v1math.NA공통 태그 Stochastic Optimization, convergence analysis

폐루프 생성 선택: 수렴, 메모리, 그리고 노이즈 오라클

Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

폐루프 생성 선택은 계산 약물 발견의 핵심 방법이 되었다. 학습된 생성 모델이 후보 분자를 제안하고, 적합도(fitness) 오라클이 이를 점수화하며, 최상의 후보들이 유지된 뒤 다음 라운드 전에 모델이 이 엘리트 집합으로 재학습된다. 널리 사용됨에도 불구하고, 이 방법은 엄밀한 수렴 이론이 부족했다. 이는 주로 매 라운드마다 모델을 재학습하면 고전적 진화 알고리즘 분석이 의존하는 마르코프(Markov) 성질이 깨지기 때문이다. 우리는 이 클래스의 알고리즘에 대한 자급자족적인 수렴 이론과 기대 실행 시간 이론을 개발한다. 확장된 상태 공간에서 마르코프 구조를 복원함으로써, 엘리티즘(elitism)이 탐색을 흡수(absorbing)하게 만든다는 것을 보이고, 거의 확실(almost-sure) 수렴과 함께 탐색을 각 적합도 수준을 탈출하는 데 소요된 시간으로 분해하는 실행 시간 상한을 증명한다. 그런 다음 모델의 메모리—과거 데이터 중 얼마나 많은 부분으로 학습하는지—의 역할을 분석한다. 학습이 더 많은 데이터로 꾸준히 개선될 때, 더 깊은 메모리는 결코 해가 되지 않는다. 그렇지 않을 때, 탈출 시간(exit-time) 분석은 최적 메모리 깊이를 특정하고, 과도한 메모리가 실제로 수렴을 느리게 할 수 있음을 보인다. 이론은 다목적 탐색과 노이즈 오라클로 확장된다. 경꼬리(light-tailed) 노이즈 하에서 몇 번의 반복 평가가 진행을 보증하는지, 그리고 견고(robust) 추정량이 중괄꼬리(heavy-tailed) 하에서 보장을 어떻게 복원하는지를 정량화한다. 약물 설계의 진정한 병목인 오라클 평가의 관점에서 재구성하면, 분석은 구체적이고 평가를 최소화하는 전략을 제공한다. 재현 가능한 연구가 예측을 확인하며, 여기에는 과도한 메모리의 놀라운 비용도 포함된다. 우리는 세 가지 미해결 문제로 마무리한다.

arXiv:2607.14731v1cs.LG공통 태그 Stochastic Optimization, convergence analysis

평활성 상수에는 무엇이 담겨 있는가? 유계 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.12172v1cs.DC공통 태그 Distributed Optimization, Stochastic Optimization

분산 경사하강법: 병목 구간과 예산 복잡도

Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity

분산 경사하강법(decentralized gradient descent, DGD)은 에이전트 네트워크에서 분산 최적화 문제를 풀기 위해 널리 사용된다. 수렴 특성은 잘 이해되어 있지만, 규정된 정확도를 달성하는 데 필요한 통신 및 계산 자원에 대해서는 상대적으로 덜 알려져 있다. 본 논문에서는 자원 인식(resource-aware) 관점에서 DGD를 연구하고, 목표 오차 수준을 달성하는 데 필요한 통신-계산 예산을 특성화한다. 우리는 서로 다른 오차 규모에서 최적화 역학을 지배하는 요인이 달라지는 병목 중심(bottleneck-centric) 프레임워크를 제안한다. 구체적으로 초기화, 목적 함수 이질성(objective heterogeneity) 및 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈가 지배하는 동작 구간을 식별한다. 이러한 효과를 포착하기 위해 두 가지 기본량인 그래디언트 다양성 대 네트워크 연결성 비율(gradient-Diversity-to-Network-connectivity Ratio, DNR)과 그래디언트 대 통신 노이즈 비율(Gradient-to-Communication-noise Ratio, GCR)을 도입한다. 이들이 최적화 과정에서 순차적으로 등장하는 병목의 순서와 그에 대응하는 예산 최적 동작 전략을 결정함을 보인다. 다단계 분석을 통해 규정된 정확도 달성에 필요한 예산 자원을 정량화하는 최적 보폭(stepsize) 선택과 명시적 예산-복잡도 상한을 도출한다. 결과 식은 전체 예산이 연속적인 병목에 대응하는 기여로 어떻게 분해되는지 밝히고, 목적 함수 이질성, 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈 사이의 근본적 트레이드오프에 대한 통찰을 제공한다.

arXiv:2607.12360v1cs.LG공통 태그 Stochastic Optimization, signsgd

같은 손실, 같은 노이즈, 반대 스케줄: 노이즈 구조와 옵티마이저 정규화가 학습률 쿨다운 효과를 공동으로 결정한다

Same Loss, Same Noise, Opposite Schedules: Noise Structure and Optimizer Normalization Jointly Determine Whether Learning-Rate Cooldown Helps

warmup-stable-decay(WSD) 학습률 스케줄의 쿨다운 단계는 대규모 모델 사전학습에서 이제 기본값이 되었으며, 어떤 설정에서는 최종 학습 손실을 낮추지만 다른 설정에서는 아무 효과도 없다. 우리는 어떤 경우가 성립하는지에 대한 증명 가능한 설명을 제공하며, 이는 두 가지 성질, 즉 그래디언트 노이즈의 구조와 옵티마이저가 업데이트를 정규화하는지 여부에 함께 달려 있다. 강볼록 목적함수와 곱셈적(그래디언트 비례) 노이즈 하에서 확률적 경사하강법은 일정한 학습률에서 기하학적으로 수축하므로 쿨다운이 개선할 여지가 없다. 동일한 목적함수와 노이즈 하에서 적응형 옵티마이저의 표준 대리인 부호 기반 및 정규화 방법들은 $η^2$ 차수의 노이즈 바닥에 정착하며, 학습률이 0으로 수렴할 때에만 최솟값에 도달한다. 반면 가산 노이즈가 있으면 모든 방법에 대해 바닥이 다시 나타난다. 메커니즘은 기본적이다. SGD 단계는 그래디언트에 비례하여 축소되므로 스스로 어닐링되지만, 정규화된 단계는 단위 스케일을 유지하므로 그렇지 못한다. 우리는 이차 목적함수에서 signSGD 정상 법칙을 정확히 풀어 바닥 상수를 닫힌 형태로 얻고, $(L_0,L_1)$-매끄러움 하에서 분리의 국소 형태를 증명하며, 스케일 불변성 논증을 통해 차원 d>1에서 정규화 SGD로 바닥을 확장하고, 모멘텀과 heavy-tailed 노이즈에 대한 견고성을 확립한다. 시뮬레이션은 모든 예측을 확인하며, 우리는 직접 측정된 그래디언트 노이즈를 사용한 실제 분류 작업에서 그 결과로 얻은 노이즈 체제 진단을 시연한다. 이 메커니즘은 쿨다운이 도움이 되는지 여부를 설명하며, 대규모에서 사용되는 내부 쿨다운 비율은 정상 상태의 landscape-노이즈 기하 밖에 있다.

arXiv:2607.10263v1cs.LG공통 태그 Stochastic Optimization, convergence analysis

이중 레벨 최적화를 위한 단일 루프 방법의 정밀 분석

Sharper Analysis of Single-Loop Methods for Bilevel Optimization

이중 레벨 최적화(bilevel optimization)는 하이퍼파라미터 최적화, 메타 학습(meta-learning), 신경망 구조 탐색(neural architecture search), 강화학습 등 다양한 머신러닝 응용의 기반이 된다. 하이퍼그래디언트(hypergradient) 기반 방법들이 크게 발전하였음에도, 이론적 보장과 효율성을 위해 요구되는 실용적인 단일 루프(single-loop) 구현 사이의 격차는 여전히 존재한다. 본 논문에서는 제안하는 분석 프레임워크인 분리 노름 분석(decoupled norm analysis, DNA)을 활용하여, 단일 루프 근사 암묵적 미분(AID)과 반복 미분(ITD) 방법의 보다 정밀한 수렴 결과를 확립함으로써 이 격차를 해소한다. AID의 경우, 수렴 속도를 $\mathcal{O}(κ^6/K)$에서 $\mathcal{O}(κ^5/K)$로 개선하였으며, 여기서 $κ$는 내부 레벨 문제의 조건수(condition number)이다. ITD의 경우, 점근 오차가 $\mathcal{O}(κ^2)$임을 증명하여 기존의 알려진 하한(lower bound)과 정확히 일치하며 이전의 $\mathcal{O}(κ^3)$ 보장을 개선하였다. 합성 및 실제 태스크에 대한 수치 실험이 이론적 결과를 뒷받침한다.

토론

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