거리 의존적 모멘트 조건에서의 일반적인 비볼록 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 최적성 진술은 추가적인 오라클 구조를 통해 더 빠른 알고리즘이 허용되는 더 좁은 평균 제곱 평활 클래스와 구별됩니다.
원문 초록
Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2Δ^3\varepsilon^{-6}$ and $LΔσ^2\varepsilon^{-4}$ stochastic terms, where $Δ$ is the initial objective gap and $σ^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
제약 조건이 있는 비평활 비볼록 확률적 최적화를 위한 최적 알고리즘
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)을 기반으로 합니다.
하강 방향으로부터 학습: 일방 Hölder 정칙성 하의 적응형 경사하강법
Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity
연속 미분 가능하고 비볼록일 수 있는 목적함수에 대해, 일방 Hölder 정칙성 하에서 적응형 경사하강법을 연구한다. 고전적인 Hölder 또는 Lipschitz 그래디언트 가정과 달리, 후자는 전체 그래디언트 변화를 제어하는 반면, 우리의 조건은 하강 부등식에 나타나는 방향 항만을 제한한다. 이는 그래디언트 변화가 크더라도 업데이트 방향에 직교하거나, 그 방향을 따라 유리한 경우 보다 덜 보수적인 스텝 크기를 허용할 수 있다. 양의 일방 Hölder 곡률 추정에 기반한 적응형 스칼라 스텝 방법을 제안하며, 이를 간단한 충분 감소(sufficient-decrease) 보호 장치와 결합한다. 수용된 업데이트 구간을 포함하는 볼록 영역 위의 비볼록 목적함수에 대해, Hölder 지수에 의해 결정되는 명시적 최적 반복 정류(stationarity) 한계를 증명한다. 미리 정해진 감소 스텝 크기 스킴과 달리, 이 방법은 국소 하강 기하에 적응한다. 방향 곡률과 전체 그래디언트 변화를 분리하도록 설계된 두 개의 풀 배치(full-batch) 벤치마크에서 접근법을 평가한다. 이진 분류 문제에서, 이 방법은 비교된 스칼라 그래디언트 방법들 중 최종 교차 엔트로피, 목적함수 값, 그래디언트 노름이 가장 낮고, 분류 마진이 가장 크다. 비볼록 Hölder 회귀 문제에서, 최종 목적함수 간극과 그래디언트 노름이 가장 낮다. 이 결과는 전체 그래디언트 변화가 하강을 방해하지 않는 방향으로 인해 부풀려질 때, 일방 Hölder 곡률이 효과적인 적응형 스텝 크기 신호임을 시사한다.
데이터 과학의 수학
Mathematics of Data Science
이 책은 데이터 과학의 수학적 기초에 관한 것이다. 1. 서론 2. 고차원에서의 저주, 축복, 그리고 놀라움 3. 특이값 분해(SVD)와 주성분 분석(PCA) 4. 선형 회귀와 정규화 5. 그래프, 네트워크, 그리고 클러스터링 6. 비선형 차원 축소와 확산 맵(Diffusion Maps) 7. 랜덤 투영을 통한 선형 차원 축소 8. 데이터 과학을 위한 최적화 9. 분류 10. 심층 학습의 수학적 소개 11. 그래프 라플라시안의 대표본 극한 12. 커뮤니티 13. 측도 집중과 가우시안 분석 14. 행렬 집중 부등식 15. 압축 센싱과 희소성 16. 저계수 행렬 복원
비볼록 최적화에서의 스케줄-프리 방법 이해: 수렴률 보장과 안장점 탈출
Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles
스케줄-프리(Schedule-Free) 방법은 학습률 스케줄러의 설계 및 튜닝 부담을 완화하면서도 튜닝된 스케줄러를 사용하는 최적화 기법과 동등하거나 때로는 이를 능가하는 성능을 보여 점점 더 많은 관심을 받고 있다. 이러한 강력한 실증적 결과에도 불구하고, 현대 머신러닝 목적 함수가 주로 발생하는 비볼록(nonconvex) 최적화 환경에서의 수렴 이론은 거의 탐구되지 않은 채로 남아 있었다. 본 논문에서는 보조적 수정이나 제한적 조건 없이 표준 형태의 스케줄-프리 경사하강법과 스케줄-프리 확률적 경사하강법에 대해, 매끄럽지만 비볼록일 수 있는 목적 함수에 대한 최악의 경우(worst-case) 분석을 제공한다. 이 방법들과 연관된 연속 시간 극한 상미분방정식으로부터 도출한 Lyapunov 분석을 기반으로, 스케줄-프리 경사하강법과 스케줄-프리 확률적 경사하강법이 1차 방법들 중 달성 가능한 최적의 최악의 경우 수렴률을 달성함을 보인다. 나아가 스케줄-프리 경사하강법을 비자율 동역학 시스템으로 정식화하고, 임의로 작은 일회성 섭동 하에서 엄격한 안장점(strict saddle) 회피를 증명한다. 이러한 이론적 결과들은 스케줄-프리 방법이 보여주는 강력한 성능에 대한 더 나은 이해를 제공한다.
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
비매끄 비볼록 최적화에서 Adam의 수렴
Adam Converges in Nonsmooth Nonconvex Optimization
Adam은 가장 널리 구현되고 영향력 있는 현대 최적화기 중 하나이다. 실제로 다양한 최적화 문제에서 왜 효과적인가? 이 질문은 지난 10년간 최적화 커뮤니티의 중심에 있다고 할 수 있으며, Adam의 수렴 거동을 이해하려는 방대한 연구를 이끌어왔다. 그러나 기존 연구는 주로 매끄 비볼록 최적화에서 Adam의 수렴률에 초점을 맞춰왔는데, 신경망 학습 등에서 나타나는 것처럼 많은 실제 문제가 비매끄하기 때문에 실용적 설정을 충분히 반영하지 못한다. 따라서 이러한 연구만으로는 Adam의 인기와 경험적 성공을 완전히 설명할 수 없다. 최근 Online-to-Nonconvex Conversion이라는 통찰력 있고 강력한 프레임워크가 비매끄 비볼록 최적화에서 Adam을 분석하는 새로운 방법을 열었다. 불행히도 이 계열의 선행 연구들은 두 가지 공통된 한계를 공유한다. 첫째, 모두 원래 Adam 알고리즘의 중요한 바이어스 보정 항을 무시한다. 둘째, 더 중요하게는 많은 연구가 클리핑 단계와 같이 Adam에서 사용되지 않는 추가 연산을 요구한다. 따라서 원래 Adam 방법에 대한 수렴 보장은 여전히 불분명하다. 본 연구에서는 바이어스 보정 단계를 포함하고 추가적인 알고리즘 수정 없이 Adam의 고전적 형태에 대한 최초의 유한 시간 분석을 제시하며, 무작위로 스케일링된 학습률이 비매끄 비볼록 최적화에서 $1/T^{\frac{2}{13}}$의 수렴률을 보장함을 증명한다. 더 나아가, 본 결과는 실제에 더 가까운 현대적인 heavy-tailed noise 영역에 엄밀히 적용된다. 흥미롭게도, 본 이론은 최근 경험적 연구들과 부합하는 매개변수 선택 $β_1=β_2$ 하에서 확립된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.