원문 초록
We exhibit a simple deterministic one-dimensional convex composite optimization problem for which AdaGrad scheme does not achieve the classical convergence rate $\mathcal{O}(n^{-(1+ν)/2})$ associated with Hölder-smooth objectives. The example highlights a basic mismatch between classical AdaGrad accumulation and composite optimality. A main insight is that the gradient of the smooth term may not vanish at the optimum, causing AdaGrad to keep reducing its stepsize excessively and converge more slowly. We also discuss why alternative accumulation mechanisms based on gradient mappings or on successive gradient differences, avoid this pathology.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.29893v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
평활성 상수에는 무엇이 담겨 있는가? 유계 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) 클라이언트의 영향을 어떻게 포착하는지 보여 준다.
강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
바닐라 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가 달성하는 최적 속도보다 열등함을 보이며, 이를 통해 헤비테일 노이즈 환경에서 바닐라 방법이 갖는 본질적인 한계를 밝힌다. 이론적 결과는 합성 함수에 대한 실험을 통해 뒷받침된다.
폐루프 생성 선택: 수렴, 메모리, 그리고 노이즈 오라클
Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles
폐루프 생성 선택은 계산 약물 발견의 핵심 방법이 되었다. 학습된 생성 모델이 후보 분자를 제안하고, 적합도(fitness) 오라클이 이를 점수화하며, 최상의 후보들이 유지된 뒤 다음 라운드 전에 모델이 이 엘리트 집합으로 재학습된다. 널리 사용됨에도 불구하고, 이 방법은 엄밀한 수렴 이론이 부족했다. 이는 주로 매 라운드마다 모델을 재학습하면 고전적 진화 알고리즘 분석이 의존하는 마르코프(Markov) 성질이 깨지기 때문이다. 우리는 이 클래스의 알고리즘에 대한 자급자족적인 수렴 이론과 기대 실행 시간 이론을 개발한다. 확장된 상태 공간에서 마르코프 구조를 복원함으로써, 엘리티즘(elitism)이 탐색을 흡수(absorbing)하게 만든다는 것을 보이고, 거의 확실(almost-sure) 수렴과 함께 탐색을 각 적합도 수준을 탈출하는 데 소요된 시간으로 분해하는 실행 시간 상한을 증명한다. 그런 다음 모델의 메모리—과거 데이터 중 얼마나 많은 부분으로 학습하는지—의 역할을 분석한다. 학습이 더 많은 데이터로 꾸준히 개선될 때, 더 깊은 메모리는 결코 해가 되지 않는다. 그렇지 않을 때, 탈출 시간(exit-time) 분석은 최적 메모리 깊이를 특정하고, 과도한 메모리가 실제로 수렴을 느리게 할 수 있음을 보인다. 이론은 다목적 탐색과 노이즈 오라클로 확장된다. 경꼬리(light-tailed) 노이즈 하에서 몇 번의 반복 평가가 진행을 보증하는지, 그리고 견고(robust) 추정량이 중괄꼬리(heavy-tailed) 하에서 보장을 어떻게 복원하는지를 정량화한다. 약물 설계의 진정한 병목인 오라클 평가의 관점에서 재구성하면, 분석은 구체적이고 평가를 최소화하는 전략을 제공한다. 재현 가능한 연구가 예측을 확인하며, 여기에는 과도한 메모리의 놀라운 비용도 포함된다. 우리는 세 가지 미해결 문제로 마무리한다.
Langevin Dynamics로 학습할 때 unsafe 집합 회피
Avoiding unsafe sets when training with Langevin Dynamics
노이즈가 포함된 경사하강법으로 모델을 학습하는 과정은 과감쇠(overdamped) Langevin dynamics로 이상화할 수 있으며, 자연스러운 안전성(safety) 질문은 궤적이 지정된 실패 영역 $\mathcal{A}_H$에 놓일 확률 $ν_t(\mathcal{A}_H) = \mathbb{P}(Q_t \in \mathcal{A}_H)$를 경계(bound)하는 것이다. 우리는 $d$차원에서 매끄럽고 강볼록(strongly convex)한 손실에 대해 이를 연구하며, $\mathcal{A}_H$는 최소화점(minimizer)과 에너지 갭(energy gap)으로 분리되어 있다. 학습 종료 시 평형 질량(equilibrium mass) $π(\mathcal{A}_H)$는 $d$에 대해 지수적으로 작으며, 노이즈가 작을 때는 상보적인 에너지 장벽(energy-barrier) 속도를 따른다. 궤적을 따라 형태에 무관한(shape-free) 경계 $ν_t(\mathcal{A}_H) \le π(\mathcal{A}_H)(1 + \sqrt{χ_0^2/π(\mathcal{A}_H)}\,e^{-mt})$는 집합 내(in-set) 확률이 전역 스펙트럴 갭(global spectral gap) $m$만을 사용하여 차수 $d$의 burn-in 이후 (두 배의) 정적 값으로 완화(relax)됨을 보여준다. 구체적인 Ornstein-Uhlenbeck 예시는 이 burn-in이 필요함을 보여준다. 평형 shell의 각도 슬라이스(angular slice)는 평형 질량이 매우 작음에도 불구하고 $d$에 대해 지수적인 배수만큼 일시적으로 팽창(swell)할 수 있다. 이를 배제하기 위해 Dirichlet-form Rayleigh 몫(quotient)이 아니라 영역의 중심화된(centered) indicator의 스펙트럴 측도(spectral measure)를 통해 정의된 국소 완화율(local relaxation rate)을 도입한다. 기하학적으로 고립된(geometrically isolated) 영역에 대해 이율은 전역 값을 초과하여 burn-in을 줄이며, maximum principle 상한(ceiling)과 함께 시간에 대해 균일하게(uniformly) 궤적 확률의 상한을 설정한다. 강볼록성(strong convexity)은 학습이 얼마나 빠르게 완화되는지를 정하지만, unsafe 집합의 형태는 평형으로 향하는 과정에서 궤적이 그 집합을 통해 부풀어 오르(bulge)는지 여부를 결정한다.
이중 레벨 최적화를 위한 단일 루프 방법의 정밀 분석
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)$ 보장을 개선하였다. 합성 및 실제 태스크에 대한 수치 실험이 이론적 결과를 뒷받침한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.