arXiv:2610.02258v1 cs.LG

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

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

Vaneet Aggarwal

제출 2026-09-30

한국어 초록

본 논문에서는 라운드당 하나의 편향되지 않은 확률적 서브그래디언트(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) 하한은 명시적인 조건 하에서 전체 기간 최적 보장을 유지하는 학습자에 대해 이 로그 항의 노이즈 거듭제곱을 규명합니다. 정적 비교 및 결정론적 분할도 동일한 결정으로부터 도출됩니다.

원문 초록

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $Λ_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(Λ_I+\log^2(2T))} +σDn^{1/p}(Λ_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,σ,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.

제출 이력

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

  1. arXiv:2610.02258v1

함께 살펴볼 논문

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

arXiv:2607.08104v2cs.LG공통 태그 Stochastic Optimization, 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.23676v1cs.LG공통 태그 Stochastic Optimization, 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:2606.22466v1cs.LG공통 태그 Stochastic Optimization, heavy-tailed noise

heavy-tailed 그래디언트 노이즈와 통신 노이즈 하의 연합 학습: 분산 감소 기반 알고리즘

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

연합 학습(Federated learning, FL)은 데이터를 분산·비공개 상태로 유지하면서 로컬 디바이스가 공통 모델을 공동으로 학습할 수 있게 하는 새로운 분산 머신러닝 패러다임이다. heavy-tailed 그래디언트 노이즈와 통신 노이즈가 존재하는 FL을 위해 분산 감소 기반 알고리즘 VRA-FedSGD를 제안한다. 이러한 노이즈는 무선 네트워크 및 사물인터넷(IoT) 배포 환경에서의 대규모 머신러닝에서 흔히 나타난다. VRA-FedSGD는 heavy-tailed 그래디언트 노이즈를 완화하기 위해 모멘텀 분산 감소 기법과 비선형 매핑을 함께 사용하고, heavy-tailed 통신 노이즈를 억제하기 위해 분산 감소형 집계 메커니즘을 사용한다. 평균 의미에서 VRA-FedSGD는 비볼록 목적 함수에 대해 $\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)$의 수렴률을 달성하며, 여기서 $p$는 heavy-tailed 노이즈의 꼬리 지수(tail index)이다. 거의 확실(almost sure) 의미에서 VRA-FedSGD는 강볼록 목적 함수에 대해 $\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)$의 수렴률을 달성하며, 여기서 $ε$는 임의로 작은 상수이다. 실제 데이터를 사용한 로지스틱 회귀 문제에 대한 시뮬레이션 실험으로 VRA-FedSGD의 유효성을 검증한다.

토론

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