경사하강법의 마지막 반복점은 종종 (약간) 차선책이다
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
한국어 초록
본 논문에서는 경사하강법(GD) 또는 그 확률적 변형인 확률적 경사하강법(SGD)을 사용하여 볼록 립시츠(convex Lipschitz) 함수를 최소화하는 널리 연구된 설정을 고려하고, 마지막 반복점 수렴(last iterate convergence)을 살펴봅니다. 현재까지 표준적인 보폭(stepsize) 선택을 사용할 경우 $T$단계 후 $\log T/\sqrt{T}$의 마지막 반복점 수렴 속도를 보이는 것으로 알려져 있습니다. Jain 등[2019]의 획기적인 연구에서는 비표준 보폭 시퀀스를 구성하여 최적의 $1/\sqrt{T}$ 속도를 회복했습니다. 그러나 이 시퀀스는 임의의 시간 지평(time horizon)에 적용 가능한 일반적인 보폭 스케줄과 달리 $T$를 사전에 선택해야 합니다. 또한 Jain 등은 $T$에 대한 사전 지식 없이는 어떤 보폭 시퀀스도 SGD의 마지막 반복점에 대해 최적의 오차를 보장할 수 없다고 추측했으나, 이는 지금까지 증명되지 않은 상태로 남아 있었습니다. 본 연구에서는 이 추측을 증명하며, 실제로 노이즈가 없는 GD의 경우에도 임의 시점(anytime) 마지막 반복점 보장을 고려할 때 $T$에 대한 추가적인 폴리로그(poly-log) 인수를 피하는 것이 불가능함을 보입니다.
원문 초록
We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of $\log T/\sqrt{T}$ after $T$ steps. A breakthrough result of Jain et al. [2019] recovered the optimal $1/\sqrt{T}$ rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing $T$ in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of $T$, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in $T$ when considering an anytime last iterate guarantee.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
강하게 볼록한 최적화를 위한 가속된 분산 확률적 경사하강법
Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
분산 확률적 최적화(decentralized stochastic optimization)는 네트워크 상에서의 대규모 학습을 위한 기본 패러다임으로, 에이전트가 이웃과만 통신하며 중앙 코디네이터가 필요하지 않습니다. 강하게 볼록한 문제의 경우, 통신 효율성은 주로 조건수(condition number) \(κ=L/μ\)와 네트워크 스펙트럼 갭(spectral gap) \(1-β\)에 의해 결정됩니다. 결정론적 분산 방법은 가속된 \(\sqrtκ\) 및 \(1/\sqrt{1-β}\) 의존성을 동시에 달성할 수 있지만, 기존의 확률적 방법 중에는 두 가지 개선을 동시에 달성하는 것이 없습니다. 본 논문에서는 Nesterov형 프리멀-듀얼(primal-dual) 외삽과 다중 라운드 빠른 고시프(gossip) 평균화를 결합한 분산 확률적 알고리즘인 \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD)를 제안합니다. 핵심 아이디어는 고시프 깊이를 미니배치(mini-batch) 크기와 결합하여, 추가적인 통신 라운드가 합의(consensus) 정확도를 높이고 그래디언트(gradient) 분산을 줄이도록 하는 것입니다. 우리는 MG-ADSGD가 다음의 통신 복잡도 \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] 를 달성함을 보여줍니다. 여기서 \(ε\)는 목표 정확도, \(n\)은 노드 수, \(σ^2\)는 그래디언트 분산을 나타냅니다. 우리의 아는 한, 이 바운드는 $ε$과 무관한 로그 인자를 제외하고, 분산 확률적 강하게 볼록한 최적화에 대해 현재 가능한 최고의 통신 복잡도를 제공합니다.
강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
하강 방향으로부터 학습: 일방 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 곡률이 효과적인 적응형 스텝 크기 신호임을 시사한다.
평활성 상수에는 무엇이 담겨 있는가? 유계 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) 클라이언트의 영향을 어떻게 포착하는지 보여 준다.
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)는지 여부를 결정한다.
분산 경사하강법: 병목 구간과 예산 복잡도
Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity
분산 경사하강법(decentralized gradient descent, DGD)은 에이전트 네트워크에서 분산 최적화 문제를 풀기 위해 널리 사용된다. 수렴 특성은 잘 이해되어 있지만, 규정된 정확도를 달성하는 데 필요한 통신 및 계산 자원에 대해서는 상대적으로 덜 알려져 있다. 본 논문에서는 자원 인식(resource-aware) 관점에서 DGD를 연구하고, 목표 오차 수준을 달성하는 데 필요한 통신-계산 예산을 특성화한다. 우리는 서로 다른 오차 규모에서 최적화 역학을 지배하는 요인이 달라지는 병목 중심(bottleneck-centric) 프레임워크를 제안한다. 구체적으로 초기화, 목적 함수 이질성(objective heterogeneity) 및 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈가 지배하는 동작 구간을 식별한다. 이러한 효과를 포착하기 위해 두 가지 기본량인 그래디언트 다양성 대 네트워크 연결성 비율(gradient-Diversity-to-Network-connectivity Ratio, DNR)과 그래디언트 대 통신 노이즈 비율(Gradient-to-Communication-noise Ratio, GCR)을 도입한다. 이들이 최적화 과정에서 순차적으로 등장하는 병목의 순서와 그에 대응하는 예산 최적 동작 전략을 결정함을 보인다. 다단계 분석을 통해 규정된 정확도 달성에 필요한 예산 자원을 정량화하는 최적 보폭(stepsize) 선택과 명시적 예산-복잡도 상한을 도출한다. 결과 식은 전체 예산이 연속적인 병목에 대응하는 기여로 어떻게 분해되는지 밝히고, 목적 함수 이질성, 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈 사이의 근본적 트레이드오프에 대한 통찰을 제공한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
NeurIPS 2026