arXiv:2606.22326v1 math.OC

비매끄 비볼록 최적화에서 Adam의 수렴

Adam Converges in Nonsmooth Nonconvex Optimization

Zijian Liu

제출 2026-06-21

한국어 초록

Adam은 가장 널리 구현되고 영향력 있는 현대 최적화기 중 하나이다. 실제로 다양한 최적화 문제에서 왜 효과적인가? 이 질문은 지난 10년간 최적화 커뮤니티의 중심에 있다고 할 수 있으며, Adam의 수렴 거동을 이해하려는 방대한 연구를 이끌어왔다. 그러나 기존 연구는 주로 매끄 비볼록 최적화에서 Adam의 수렴률에 초점을 맞춰왔는데, 신경망 학습 등에서 나타나는 것처럼 많은 실제 문제가 비매끄하기 때문에 실용적 설정을 충분히 반영하지 못한다. 따라서 이러한 연구만으로는 Adam의 인기와 경험적 성공을 완전히 설명할 수 없다. 최근 Online-to-Nonconvex Conversion이라는 통찰력 있고 강력한 프레임워크가 비매끄 비볼록 최적화에서 Adam을 분석하는 새로운 방법을 열었다. 불행히도 이 계열의 선행 연구들은 두 가지 공통된 한계를 공유한다. 첫째, 모두 원래 Adam 알고리즘의 중요한 바이어스 보정 항을 무시한다. 둘째, 더 중요하게는 많은 연구가 클리핑 단계와 같이 Adam에서 사용되지 않는 추가 연산을 요구한다. 따라서 원래 Adam 방법에 대한 수렴 보장은 여전히 불분명하다. 본 연구에서는 바이어스 보정 단계를 포함하고 추가적인 알고리즘 수정 없이 Adam의 고전적 형태에 대한 최초의 유한 시간 분석을 제시하며, 무작위로 스케일링된 학습률이 비매끄 비볼록 최적화에서 $1/T^{\frac{2}{13}}$의 수렴률을 보장함을 증명한다. 더 나아가, 본 결과는 실제에 더 가까운 현대적인 heavy-tailed noise 영역에 엄밀히 적용된다. 흥미롭게도, 본 이론은 최근 경험적 연구들과 부합하는 매개변수 선택 $β_1=β_2$ 하에서 확립된다.

원문 초록

Adam is one of the most widely implemented and influential modern optimizers. Why is it effective across different optimization problems in practice? This question arguably lies at the center of the optimization community over the last decade and has motivated a substantial body of work aimed at understanding its convergence behavior. However, existing studies have mainly focused on the convergence rate of Adam in smooth nonconvex optimization, which unfortunately does not adequately capture practical settings, since many real-world problems are nonsmooth, such as those arising in training neural networks. Thus, these studies cannot fully explain the popularity and empirical success of Adam. Recently, an insightful and powerful framework called Online-to-Nonconvex Conversion has opened a new way to analyze Adam for nonsmooth nonconvex optimization. Unfortunately, prior works along this line share two common limitations. First, all of them ignore the important bias-correction term in the original Adam algorithm. Second and more importantly, many of them require extra operations that are not used in Adam, such as a clipping step. Therefore, the convergence guarantee for the original Adam method still remains unclear. In this work, we present the first finite-time analysis for the classical form of Adam, i.e., with the bias-correction step and without further algorithmic modifications, and prove that a randomly scaled learning rate ensures a convergence rate of $1/T^{\frac{2}{13}}$ for nonsmooth nonconvex optimization. Moreover, our result provably applies to the modern heavy-tailed noise regime, which is closer to practice. Interestingly, our theory is established under the parameter choice $β_1=β_2$, aligning with the recent empirical studies.

요약

바이어스 보정을 포함한 원래 Adam 알고리즘에 대해 비매끄 비볼록 최적화에서의 최초 유한 시간 수렴 분석을 제시하며, 무작위 스케일링 학습률 하에서 $1/T^{2/13}$ 수렴률을 증명한다. heavy-tailed noise 영역에도 적용되며, 이론은 최근 경험적 연구와 맞는 $β_1=β_2$ 매개변수 선택 하에서 성립한다.

제출 이력

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

  1. arXiv:2606.22326v1제출 시각 미확인

함께 살펴볼 논문

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

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

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

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

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

arXiv:2606.28879v1cs.LG공통 태그 Stochastic Optimization, adam optimizer, convergence analysis

확률적 동적 시스템을 위한 Adam 알고리즘 분석

Analysis of Adam Algorithms for Stochastic Dynamic Systems

적응형 모멘텀 추정 알고리즘인 Adam은 반복당 낮은 계산 복잡도와 강력한 실증적 성능 덕분에 현대 머신러닝에서 널리 사용된다. 광범위하게 활용됨에도 불구하고, Adam의 이론적 기반은 시변(time-varying) 및 비정상(nonstationary) 시스템에 대해 대부분 미개척 상태로 남아 있다. 실제로 Adam 유형 알고리즘의 기존 이론적 분석은 주로 시불변(time-invariant) 모델 매개변수를 다루며, 독립 동일 분포(i.i.d.) 데이터 가정에 명시적 또는 묵시적으로 의존한다. 이 가정 하에서는 학습 과제가 정적 최소화 지점을 가진 고정된 기대 목적 함수를 최소화하는 문제로 정식화될 수 있다. 그러나 이러한 가정은 시변 및 비정상 시스템에서 종종 위반되므로, 기존의 이상화된 i.i.d. 환경을 넘어서는 이론적 탐구가 요구된다. 본 논문의 주요 목표는 시변 및 비정상 확률적 시스템을 위한 Adam의 일반 이론을 수립함으로써 이 어려운 문제를 해결하는 것이다. 우리는 Adam의 결합된 1차 및 2차 모멘텀 점화식(recursion)에 의해 유도되는 비정상적이고 종속적인 랜덤 행렬의 곱을 분석하기 위한 새로운 기법을 도입하고, 두 모멘텀 동역학을 결합하는 새로운 확률적 Lyapunov 함수를 구성한다. 비정상적이고 종속적인 데이터를 허용하는 확률적 여기(excitation) 조건 하에서, 매개변수 추적 및 출력 예측 오차 한계를 명시적으로 도출하여 스텝 크기, 1차 및 2차 모멘텀 매개변수, 그래디언트 잡음, 매개변수 드리프트의 영향을 정량화한다. 이러한 한계는 Adam 성능에 대한 보장을 제공할 뿐만 아니라 하이퍼파라미터 선택을 위한 지침도 제공한다. 합성 데이터와 실세계 데이터 모두에 대한 실험이 우리의 이론과 설계 지침을 검증한다.

arXiv:2610.13787v1math.OC공통 태그 Stochastic Optimization, nonconvex optimization

제약 조건이 있는 비평활 비볼록 확률적 최적화를 위한 최적 알고리즘

Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints

본 논문에서는 볼록 제약 집합 하에서 목적 함수가 평활(smooth)하지도 볼록(convex)하지도 않은 확률적 최적화(stochastic optimization) 문제를 위한 새로운 알고리즘을 제시합니다. 제안하는 알고리즘은 제약이 있는 문제에 대해 Liu et al. (2024)이 최근 정의한 $(δ,\varepsilon)$-골드스타인 정상점($(δ,\varepsilon)$-Goldstein stationary point)을 향상된 복잡도로 반환하며, 여러 설정에서 이 작업에 대해 최초로 최적의 수렴(convergence) 속도를 달성합니다. 구체적으로, 확률적 기울기(stochastic gradient)를 사용하여 최적임을 증명한 $\widetilde O(δ^{-1}\varepsilon^{-3})$ 속도를 달성하는 투영 기반(projection-based) 및 무투영(projection-free) 알고리즘을 설계하고, 0차 쿼리(zeroth-order queries)를 사용하여 차원 $d$에 대한 의존성 측면에서 최적이자 기존 연구를 개선한 $\widetilde O(dδ^{-1}\varepsilon^{-3})$ 속도를 달성합니다. 특히, 우리의 하한(lower bound)은 프랭크-울프 갭(Frank-Wolfe gap) 관점에서 제시되며 평활한 문제에서도 성립하므로 독립적인 관심 대상이 됩니다. 이러한 결과는 비볼록 확률적 최적화에서 제약 조건의 존재나 비평활성 모두에 의해 수렴 속도가 저하되지 않음을 보여줍니다. 본 분석은 제약 없는 최적화의 관련 기법을 확장하여 온라인 선형 최적화(online linear optimization)로의 귀약(reduction)을 기반으로 합니다.

arXiv:2606.03904v2cs.LG공통 태그 Stochastic Optimization, adam optimizer

MAdam: 메트릭 인식 다중 목적 Adam

MAdam: Metric-Aware Multi-Objective Adam

다중 목적 최적화(MOO)는 수많은 머신러닝 문제의 기반을 이루지만, 손실 균형(loss-balancing), 그래디언트 균형(gradient-balancing), 파레토(Pareto) 기반 계열 전반의 MOO 솔버들은 절충된 방향 벡터를 거의 예외 없이 Adam~\citep{kingma2015adam}에 전달합니다. 본 논문에서는 이러한 결합으로 인해 솔버의 의도와 옵티마이저의 실행 사이에 두 가지 구조적 괴리가 발생함을 보입니다. 첫 번째는 가중치 불일치(weighting mismatch)입니다. Adam의 2차 모멘트 분모는 시간에 따라 변하는 선호도(preference) 벡터와 그래디언트 통계량을 뒤엉키게 만들어, 선호도를 과거 이력의 평균으로 한계화하고 서로 다른 파레토 절충안들을 거의 균일한 혼합 상태로 수렴시켜 버립니다. 두 번째는 기하학적 불일치(geometric mismatch)입니다. Adam의 적응형 메트릭은 MOO 솔버가 가정하는 유클리드 기하학을 왜곡하여, 정렬된 목적들을 표면상 충돌하는 것처럼 변형시킵니다. 이 두 문제를 동시에 해결하기 위해, 솔버와 옵티마이저를 전혀 변경하지 않고 그대로 사용할 수 있는 드롭인 래퍼(drop-in wrapper)인 MAdam(Metric-Aware Multi-Objective Adam)을 제안합니다. MAdam은 스칼라화된 목적 함수의 선호도 조건부 곡률(curvature)로 절충된 방향을 사전조건화(preconditioning)합니다. 이처럼 백색화(whitening)된 입력에서 Adam의 2차 모멘트는 단위행렬로 단순화되므로, 실제 반영되는 업데이트는 선호도 조건부 메트릭에 의해 제어됩니다. 멀티태스크 학습, 파레토 전선 복원, 물리 정보 신경망(PINN), 의료 영상 전반에 걸쳐 MAdam은 모든 솔버 계열에 대해 전반적으로 Adam 대비 성능을 향상시킵니다. 코드는 https://github.com/lfb-1/MAdam 에서 제공됩니다.

arXiv:2609.30499v2stat.ML공통 태그 Stochastic Optimization, nonconvex optimization

거리 의존적 모멘트 조건에서의 일반적인 비볼록 SGD: 유한 시계 정지성과 나가예프 한계

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

균일한 노이즈 모멘트 한계 조건은 반복점(iterate)에 따라 변동성이 증가하는 확률적 그래디언트를 배제합니다. 본 논문에서는 거리 의존적인 조건부 모멘트 하에서, 매끄럽고 하한이 있는 비볼록(nonconvex) 목적 함수에 대한 일반적인 단일 샘플 확률적 경사하강법(SGD)을 연구합니다. 2차 모멘트 조건만으로도 직접적인 하강-변위(descent--displacement) 논증을 통해 시계 의존적 스텝사이즈를 갖는 $T^{-1/3}$ 기대 평균 제곱 그래디언트 정지성을 도출합니다. 명시적인 오라클 복잡도 따름정리는 $Δ$가 초기 목적 함수 차이이고 $σ^2+b_2\|x-x_1\|^2$가 분산을 제한할 때 $Lb_2Δ^3\varepsilon^{-6}$ 및 $LΔσ^2\varepsilon^{-4}$ 확률적 항을 포함하여 기존에 알려진 매끄러운 블룸-글라디셰프(Blum--Gladyshev, BG-0) 하한과 일치합니다. 따라서 수정되지 않은 일반 SGD는 이 2차 모멘트 클래스에서 미니맥스 확률적 복잡도를 달성합니다. $p>2$인 경우, 예측 가능한 국소화(localization)와 힐베르트 공간 푹-나가예프(Fuk--Nagaev) 부등식을 통해 로그 분산과 다항식 희귀 충격(rare-shock) 기여를 분리하는 높은 확률 한계를 얻습니다. 국소화 반경은 재귀식으로부터 유도되므로, 유계 반복점 가정, 클리핑, 정규화(normalization), 모멘텀(momentum) 또는 증가하는 배치(batch) 크기가 필요하지 않습니다. 또한 신뢰도 증가율(increasing-confidence rates), $\sqrt{T}$ 정지성을 회복하는 목적 함수 차이 성장 개선, 그리고 확률적 $L^p$-립시츠 예시를 제시합니다. 광범위한 BG-0 최적성 진술은 추가적인 오라클 구조를 통해 더 빠른 알고리즘이 허용되는 더 좁은 평균 제곱 평활 클래스와 구별됩니다.

arXiv:2608.20638v2cs.LG공통 태그 Stochastic Optimization, adam optimizer

안정성의 한계(Edge of Stability)에 선 Adam: 적응형 피드백, 증명 가능한 진동, 그리고 그래디언트 반전

Adam at the Edge of Stability: Adaptive Feedback, Provable Oscillation, and Gradient Reversal

풀배치(full-batch) Adam에서 나타나는 안정성의 한계(Edge of Stability, EoS) 현상은 널리 관찰되어 왔지만, 그 기저에 있는 동역학적 메커니즘은 여전히 명확히 이해되지 않았습니다. 본 논문에서는 Adam의 2차 모멘트 적응을 동역학을 안정성 경계로 이끄는 음의 피드백 메커니즘으로 규명합니다. 우리는 이러한 메커니즘을 사전조건화된 그래디언트 방향을 따른 사전조건화된 곡률인 *활성 곡률(active curvature)*을 통해 규정하며, 점진적으로 확장되는 설정에서 엄밀한 특성화를 확립합니다: 모멘텀이 포함된 랭크-1 2차 함수, 활성 곡률이 선명도(sharpness)와 분리되는 대각 2차 함수, 그리고 일반적인 목적 함수. 중요한 점은, 이 메커니즘이 한계 부근에서 풀배치 Adam의 *그래디언트 반전(gradient reversal)*을 예측한다는 것입니다. 즉, 완전 연결 신경망, ResNet, ViT, LSTM, GPT-2 medium, 그리고 Adam 계열 옵티마이저 전반에서 관찰되는 것처럼 연속된 그래디언트가 반복적으로 거의 반대 방향을 가리키게 됩니다. 이러한 양상과 일치하게, 반복값(iterates)을 평균화하면 이러한 빠른 진동이 억제되고 더 매끄럽고 낮은 손실 곡선이 생성됩니다. 종합적으로, 이러한 결과들은 활성 곡률과 그래디언트 반전을 통해 Adam의 EoS 동역학적 동작을 완전히 이해하기 위한 중요한 첫걸음을 제공합니다.

토론

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