arXiv:2508.04860v2 math.OC

SGD는 헤비테일 노이즈를 다룰 수 있는가?

Can SGD Handle Heavy-Tailed Noise?

Ilyas Fatkhullin, Florian Hübler, Guanghui Lan

제출 2025-08-06

저자 비고

arXiv Comments

40 pages, 5 figures, 2 tables. Extended version of a paper accepted for publication in the SIAM Journal on Optimization

한국어 초록

확률적 경사하강법(SGD)은 대규모 최적화(optimization)의 초석이지만, 현대 머신러닝과 강화학습(RL)에서 흔히 발생하는 헤비테일(heavy-tailed) 노이즈 하에서의 이론적 동작은 여전히 잘 이해되지 않고 있습니다. 본 연구에서는 어떠한 적응형 수정도 거치지 않은 바닐라 SGD가 이러한 불리한 확률적 조건 하에서 이론적으로 성공할 수 있는지를 엄밀하게 조사합니다. 확률적 그래디언트(stochastic gradient)가 특정 $p \in (1, 2]$에 대해 유계 $p$차 모멘트를 가진다는 가정만을 바탕으로, 볼록(convex), 강볼록(strongly convex), 비볼록(non-convex) 문제 클래스 전반에 걸쳐 (사영) SGD에 대한 정밀한 수렴(convergence) 보장을 확립합니다. 특히 볼록 및 강볼록 영역에서 최소한의 가정 하에 SGD가 각각 $\mathcal{O}(\varepsilon^{-\frac{p}{p-1}})$ 및 $\mathcal{O}(\varepsilon^{-\frac{p}{2(p-1)}})$의 미니맥스 최적 표본 복잡도(sample complexity)를 달성함을 보여줍니다. 비볼록 목적 함수에 대해서는 표준적인 매끄러움(smoothness)과 유계 중심 $p$차 모멘트 하에서 $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ 복잡도로 정류점(stationary point)에 수렴함을 증명하며, 이에 일치하는 SGD 전용 하한을 보완하여 어떠한 결정론적 양의 비증가 학습률(step-size) 스케줄로도 이 속도를 향상시킬 수 없음을 보여줍니다. 이러한 결과는 헤비테일 노이즈가 SGD를 비효율적으로 만든다는 지배적인 관점에 도전하며, 분산이 무한한 영역에서도 바닐라 SGD가 견고하고 이론적으로 원칙에 입각한 기준선(baseline)임을 확립합니다.

원문 초록

Stochastic Gradient Descent (SGD) is a cornerstone of large-scale optimization, yet its theoretical behavior under heavy-tailed noise -- common in modern machine learning and reinforcement learning -- remains poorly understood. In this work, we rigorously investigate whether vanilla SGD, devoid of any adaptive modifications, can provably succeed under such adverse stochastic conditions. Assuming only that stochastic gradients have bounded $p$-th moments for some $p \in (1, 2]$, we establish sharp convergence guarantees for (projected) SGD across convex, strongly convex, and non-convex problem classes. In particular, we show that SGD achieves minimax optimal sample complexity under minimal assumptions in the convex and strongly convex regimes: $\mathcal{O}(\varepsilon^{-\frac{p}{p-1}})$ and $\mathcal{O}(\varepsilon^{-\frac{p}{2(p-1)}})$, respectively. For non-convex objectives, under standard smoothness and a bounded central $p$-th moment, we prove convergence to a stationary point with $\mathcal{O}(\varepsilon^{-\frac{2p}{p-1}})$ complexity, and complement this with a matching SGD-specific lower bound, showing that this rate cannot be improved by any deterministic positive non-increasing step-size schedule. These results challenge the prevailing view that heavy-tailed noise renders SGD ineffective, and establish vanilla SGD as a robust and theoretically principled baseline -- even in regimes where the variance is unbounded.

제출 이력

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

  1. arXiv:2508.04860v2

함께 살펴볼 논문

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

arXiv:2607.08104v2cs.LG공통 태그 Stochastic Optimization, sgd, convergence analysis, heavy-tailed noise

바닐라 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:2606.30930v1stat.ML공통 태그 Stochastic Optimization, sgd, convergence analysis

안정성의 경계에서의 SGD: 큰 학습률을 이용한 확률적 안정화

SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates

현대 심층 학습은 안정성의 경계에서 동작하며, 고전적인 최적화 이론이 정당화하는 것보다 훨씬 큰 학습률을 일상적으로 사용한다는 것이 밝혀졌다. 안정성의 경계 현상에 대한 대부분의 기존 분석은 결정론적 경사하강법에 초점을 맞추어, 확률적 환경은 대부분 미탐구 상태로 남아 있다. 본 연구에서는 선형 분류기와 2층 신경망 모두에 대해, 다중 클래스 교차 엔트로피 손실에 적용된 확률적 경사하강법(SGD)의 엄밀한 수렴 보장을 제공한다. SGD의 확률성은 곡률 기반 진동이 지배하는 안정성의 경계 레짐과, 기대 손실이 제어된 속도로 감소하는 안정적 레짐 사이를 역학이 교대로 오가도록 유발할 수 있음을 보인다. 그럼에도 불구하고, SGD가 역학을 자기 안정화(self-stabilize)함을 증명한다. 이는 반복이 고정된 횟수의 이터레이션 내에 안정성으로 복귀하도록 보장하며, 큰 학습률에서도 최선 반복(best-iterate) 의미에서의 수렴을 가능하게 한다. 실험을 통해 이론적 결과를 검증하고, 큰 스텝 크기 레짐에서 SGD의 이점을 보여준다.

arXiv:2606.23676v1cs.LG공통 태그 Stochastic Optimization, convergence analysis, heavy-tailed noise

미해결 문제: 중(重)꼬리 노이즈 하에서 AdamW는 효과적인가?

Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?

AdamW는 대규모 언어 모델(LLM) 학습에 사실상 표준으로 쓰이는 옵티마이저이지만, 그에 대한 이론은 여전히 대부분 유한 분산 영역에 국한되어 있다. 그러나 실증적 증거는 LLM 사전학습에서 확률적 그래디언트 노이즈가 일반적으로 중(重)꼬리 분포를 따른다는 점을 보여 주므로, 이는 점점 더 불만족스러운 상황이다. 최근 연구는 Lion, Muon과 같은 부호 기반 옵티마이저가 날카로운 중(重)꼬리 수렴률을 달성함을, AdaGrad가 중(重)꼬리 노이즈 하에서도 수렴할 수 있음을 보여 주었다. 그러나 AdamW에 대한 엄밀한 수렴 이론은 아직 이 영역에서 확립되지 않았다. AdamW는 동일한 중(重)꼬리 가정 하에서 수렴할 수 있는가, 아니면 2차 모멘트 누적기가 실질적인 장애를 만드는가? 우리는 이를 미해결 문제로 공식화하고, 긍정적인 가중 메트릭(weighted-metric) 벤치마크를 증명하며, 분모 메모리(denominator memory)가 큰 그래디언트를 어떻게 숨길 수 있는지 보여 주는 회랑(corridor) 하한(lower-bound) 메커니즘을 제시한다.

arXiv:2610.02258v1cs.LG공통 태그 Stochastic Optimization, heavy-tailed noise

헤비테일 노이즈 하에서의 매개변수 없는 구간-동적 리그릿

Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

본 논문에서는 라운드당 하나의 편향되지 않은 확률적 서브그래디언트(stochastic subgradient)와 미지의 유한한 조건부 $p$차 노이즈 모멘트($1<p\le2$)를 갖는 온라인 볼록 최적화(online convex optimization)를 연구합니다. 길이 $n$의 모든 고정된 구간 $I$ 및 $\Lambda_I=1+P_I/D$를 만족하는 비교자(comparator) 경로에 대해, 한 학습자는 다음을 달성합니다: \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \] 이 학습자는 $G, \sigma, p, I, P_I$ 중 어느 것도 사용하지 않으며, 상수는 보편 상수입니다. 구간 적응(interval adaptation)은 비교자 복잡도를 증가시키면서도 서로 다른 평균 그래디언트 및 노이즈 지수를 보존합니다. 본 분석은 기댓값 측면에서 캘리브레이션을 제어하고 관측 스케일 변화에 따른 비용을 제한합니다. 일반 정리는 불균등 사전 분포(nonuniform prior)에 대한 상대 엔트로피 의존성을 바탕으로 예측 가능하게 가용한 전문가(expert)들의 분포와 비교합니다. 공통 사전 분포는 긴 윈도우와 긴 재시작 길이를 선호합니다. 제공된 통계량을 통해 구간 비용은 $1+\log(T/n)$이 되며, 전체 기간(full-horizon)에서의 최적 정적 수렴 속도(static rate)를 포함합니다. 측도 변환(change-of-measure) 하한은 명시적인 조건 하에서 전체 기간 최적 보장을 유지하는 학습자에 대해 이 로그 항의 노이즈 거듭제곱을 규명합니다. 정적 비교 및 결정론적 분할도 동일한 결정으로부터 도출됩니다.

arXiv:2609.39144v2cs.LG공통 태그 Stochastic Optimization, sgd

상수 스텝사이즈 SGD에 대한 샤프 정상 가우스 근사

Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD

본 논문에서는 외생적 균일 에르고딕 마르코프 연쇄(uniformly ergodic Markov chain)에 의해 생성되는 유계 가산 잡음(bounded additive noise)을 갖는 상수 스텝사이즈 SGD의 불변 법칙에 대해 샤프(sharp) 가우스 근사를 증명합니다. 립시츠 헤시안(Lipschitz Hessian)과 비퇴화 장기 잡음 공분산을 갖는 매끄럽고 강볼록(strongly convex)인 목적 함수에 대해, 스텝사이즈의 제곱근으로 정규화된 중심화 반복해는 1-바서슈타인 거리(1-Wasserstein distance)에서 극한 가우스 분포와 $O(\sqrtα)$만큼 가깝습니다. 이 증명은 블록 단위 가우스 비교와 장기 수축(long-run contraction)을 결합합니다. 일회성 잡음 주변 분포가 대칭이고 모든 0이 아닌 지연의 자기공분산이 소멸함에도 불구하고, 4상태 예제는 일치하는 하한을 제공합니다. 이 예제에서는 인접한 3차 혼합 모멘트가 주요 보정을 생성합니다.

arXiv:2607.23012v1cs.LG공통 태그 Stochastic Optimization, sgd

미니배치 노이즈가 지배적 부분공간 변동을 통해 샤프니스를 낮춘다

Mini-batch Noise Lowers Sharpness via Dominant-Subspace Fluctuations

SGD 학습 동안 그래디언트는 종종 손실의 헤시안 상위 $k$개 고유벡터가 생성하는 지배적 부분공간과 강하게 정렬된다. 이는 자연스럽게 손실 감소가 주로 이 공간 내에서 일어난다는 것을 시사하는 것처럼 보이지만, 선행 연구는 이 지배적 부분공간 내의 업데이트가 손실을 줄이는 데 의미 있는 진전을 이루지 못한다는 것을 보여주었다. 본 연구에서는 지배적 부분공간을 손실 감소를 위한 주요 공간이 아니라 미니배치 SGD의 샤프니스 역학을 설명하는 핵심 부분공간으로 이해하는 것이 더 적절하다고 주장한다. 상위 $k$ 샤프니스를 줄이는 데 있어 지배적 부분공간의 역할을 설명하기 위해, 지배적 방향에서의 변동에 대한 평균 그래디언트가 어떻게 샤프니스 보정 항을 생성하는지 보이고, 지배적 방향에서 미니배치 노이즈에 의해 유도되는 샤프니스 보정 항을 유도한다. 실험 결과는 유도된 보정 항을 GD에 추가하면 GD의 샤프니스 변화가 SGD의 그것에 더 가까워진다는 것을 보여준다.

토론

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