arXiv:2409.09984v2 cs.LG

증가하는 배치 크기와 감쇠하는 학습률을 활용한 샤프니스 인식 최소화 알고리즘의 수렴

Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate

Hinata Harada, Hideaki Iiduka

제출 2024-09-16

한국어 초록

샤프니스 인식 최소화(Sharpness-Aware Minimization, SAM) 알고리즘과 갭 가이드 SAM(gap guided SAM, GSAM)을 포함한 그 변형들은 학습(training) 중 경험적 손실(loss)의 평평한 국소 최소점(flat local minima)을 찾아 심층 신경망(deep neural network) 모델의 일반화 성능을 성공적으로 향상해 왔습니다. 한편, 배치(batch) 크기를 늘리거나 학습률(learning rate)을 감쇠시키면 경험적 손실의 가파른 국소 최소점(sharp local minima)을 피할 수 있다는 사실이 이론적 및 실증적으로 입증된 바 있습니다. 본 논문에서는 코사인 어닐링(cosine annealing)이나 선형 학습률과 같이 배치 크기를 늘리거나 학습률을 감쇠시키는 GSAM 알고리즘을 고려하고, 그 수렴(convergence)을 이론적으로 증명합니다. 나아가 배치 크기 증가를 적용한 SAM(GSAM)과 그렇지 않은 경우를 수치적으로 비교하여, 증가하는 배치 크기를 사용할 때 일정한 배치 크기 및 학습률을 사용하는 경우에 비해 더 낮은 최악 조건의 $\ell_\infty$ 적응형 샤프니스(adaptive sharpness)를 달성함을 보입니다.

원문 초록

The sharpness-aware minimization (SAM) algorithm and its variants, including gap guided SAM (GSAM), have been successful at improving the generalization capability of deep neural network models by finding flat local minima of the empirical loss in training. Meanwhile, it has been shown theoretically and practically that increasing the batch size or decaying the learning rate avoids sharp local minima of the empirical loss. In this paper, we consider the GSAM algorithm with increasing batch sizes or decaying learning rates, such as cosine annealing or linear learning rate, and theoretically show its convergence. Moreover, we numerically compare SAM (GSAM) with and without an increasing batch size and conclude that using an increasing batch size { achieves a lower worst-case $\ell_\infty$ adaptive sharpness} than compared with using a constant batch size and learning rate.

제출 이력

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

  1. arXiv:2409.09984v2

함께 살펴볼 논문

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

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.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)$ 보장을 개선하였다. 합성 및 실제 태스크에 대한 수치 실험이 이론적 결과를 뒷받침한다.

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

비볼록 최적화에서의 스케줄-프리 방법 이해: 수렴률 보장과 안장점 탈출

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

스케줄-프리(Schedule-Free) 방법은 학습률 스케줄러의 설계 및 튜닝 부담을 완화하면서도 튜닝된 스케줄러를 사용하는 최적화 기법과 동등하거나 때로는 이를 능가하는 성능을 보여 점점 더 많은 관심을 받고 있다. 이러한 강력한 실증적 결과에도 불구하고, 현대 머신러닝 목적 함수가 주로 발생하는 비볼록(nonconvex) 최적화 환경에서의 수렴 이론은 거의 탐구되지 않은 채로 남아 있었다. 본 논문에서는 보조적 수정이나 제한적 조건 없이 표준 형태의 스케줄-프리 경사하강법과 스케줄-프리 확률적 경사하강법에 대해, 매끄럽지만 비볼록일 수 있는 목적 함수에 대한 최악의 경우(worst-case) 분석을 제공한다. 이 방법들과 연관된 연속 시간 극한 상미분방정식으로부터 도출한 Lyapunov 분석을 기반으로, 스케줄-프리 경사하강법과 스케줄-프리 확률적 경사하강법이 1차 방법들 중 달성 가능한 최적의 최악의 경우 수렴률을 달성함을 보인다. 나아가 스케줄-프리 경사하강법을 비자율 동역학 시스템으로 정식화하고, 임의로 작은 일회성 섭동 하에서 엄격한 안장점(strict saddle) 회피를 증명한다. 이러한 이론적 결과들은 스케줄-프리 방법이 보여주는 강력한 성능에 대한 더 나은 이해를 제공한다.

토론

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