Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
원문 초록
We study the generalization properties of the popular stochastic optimization method known as stochastic gradient descent (SGD) for optimizing general non-convex loss functions. Our main contribution is providing upper bounds on the generalization error that depend on local statistics of the stochastic gradients evaluated along the path of iterates calculated by SGD. The key factors our bounds depend on are the variance of the gradients (with respect to the data distribution) and the local smoothness of the objective function along the SGD path, and the sensitivity of the loss function to perturbations to the final output. Our key technical tool is combining the information-theoretic generalization bounds previously used for analyzing randomized variants of SGD with a perturbation analysis of the iterates.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
투영 경사하강법 솔버 반복 학습의 복잡도 상한과 접근법
Complexity Bounds and Approaches to Learning Projected Gradient Descent Solver Iterates
데이터 부족은 수치적으로 계산 비용이 큰 매개변수 최적화 문제에 대한 초기 추정값을 생성하기 위해 생성 모델을 학습하는 데 근본적인 난제를 제기한다. 따라서 우리는 수렴한 해의 데이터셋을 솔버의 중간 반복값으로 보강하여 추가적인 솔버 실행 없이 학습 데이터량을 늘리는 $k$-neighborhood 데이터 수집 전략을 연구한다. 이 접근법의 이점을 이해하기 위해, 우리는 Rademacher 복잡도에 기반한 일반화 상한을 도출하여 $k$-neighborhood와 관련 매개변수의 역할을 밝힌다. 이 결과를 얻기 위해, 우리는 투영 경사하강법으로 풀리는 일측 상자 제약 2차 계획법(one-sided box-constrained quadratic programs)에 초점을 맞춘다. 우리는 두 가지 예제에서 이 솔버의 동작을 설명한다. 본 논문에서 제안하는 접근법은 데이터-모델-최적화 루프의 효율을 개선함으로써 더 유능한 DDDAS 패러다임을 가능하게 한다. 마지막으로 솔버 반복 데이터 학습에 대한 두 가지 관점을 논의하고, 우리의 분석을 새로운 데이터 효율적 전역 탐색 방법인 GLENS와 연결한다.
로컬 모집단 위험 인증서에 관하여
On Local Population-Risk Certificates
우리는 로컬 모집단 위험 증분 \(Pδ_v=R(θ_0+v)-R(θ_0)\), \(v\in\mathcal D\)에 대한 유한 표본 인증서를 개발한다. 기본 대상은 기댓값 유효 상한 끝점 \(\widehat{\mathsf U}_{\mathcal D}\)으로, \(\mathbb E\sup_{v\in\mathcal D} \{Pδ_v-\widehat{\mathsf U}_{\mathcal D}(v)\}\le0\)을 만족한다. 이 균일 기준은 동일한 표본으로부터 선택된 임의의 가측 업데이트를 인증하며, 패널티가 경험적 기하에 의존하도록 허용한다. 주된 구성은 선형 특징(feature) 클래스에 대한 교차 적합 릿지 보정이다. 파일럿 폴드가 릿지 메트릭을 학습하고, 보완 폴드가 해당 메트릭에서의 평균 제곱 오차를 보정하며, 완전 분할 평균화가 방향적 이차 형식 \(\widehat q_{X,λ}\)에서 완전 경험적 공분산을 복원한다. 최적화된 진단 척도는 \(\{\widehat q_{X,λ}(h) \widehat r_{X,n_{\rm p},λ}^{\rm cf}/n\}^{1/2}\)이며, 보정된 대각합 인수 \(\widehat r_{X,n_{\rm p},λ}^{\rm cf}\)는 통상적인 릿지 유효 차원 \(\widehat r_{X,λ}\)와 비교된다. 비매끄러운 손실의 경우, 정확한 고정 마스크 분해 \(δ_v=J_v^0+R_v^\circ+C_v\)가 고정 테일러 요동, 좋은 경로 나머지, 경계면 교차를 분리한다. 선형 및 복합 인증서를 성분별로 적용하면 동일 표본 기대 로컬 탐색 및 집중 해제 규칙에 대한 끝점을 산출한다.
고정 소수점 매개변수에 대한 경사하강법과 확률적 경사하강법의 균일 안정성과 일반화 오차
Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters
본 논문에서는 각 업데이트에 결정적 반올림(deterministic rounding) 또는 확률적 반올림(stochastic rounding)이 포함되는 이산 매개변수 공간(discrete parameter spaces)에서 경사하강법(GD)과 확률적 경사하강법(SGD)의 일반화 오차(generalization error), 균일 안정성(uniform stability), 균일 인자 안정성(uniform argument stability)을 분석합니다. 볼록(convex)하고 립시츠 연속이며 매끄러운(smooth) 손실 함수(loss functions)에 대해 결정적 반올림이 경사하강법의 일반화 오차를 악화시켜, 그 차수를 $O(T/n)$에서 $O(T/\sqrt{n})$으로 증가시킴을 보이고, 이에 부합하는 하한(lower bounds)을 확립합니다. 또한, 경사하강법의 균일 안정성이 $Ω(T)$가 됨을 증명하여, 이 설정에서 안정성 기반 일반화 바운드(stability-based generalization bounds)가 공허함(vacuous)을 보여줍니다. 대조적으로, 동일한 손실에 대해 결정적 반올림을 적용한 확률적 경사하강법은 자명하지 않은 균일 안정성 보장을 제공하는데, 이는 실수값(real-valued) 경우와 질적으로 다르며 반복 횟수와 차원(dimension)에 대해 뚜렷한 의존성을 나타냅니다: 1차원의 경우 $O(T/n)$, 고차원의 경우 $O(T^2/n)$이라는 타이트한 상한(tight bounds)을 증명합니다. 또한, 확률적 반올림(stochastic rounding)이 차원에 따라 증가하는 일반화 오차를 야기할 수 있음을 보여줍니다; 이러한 현상은 표준 실수값 최적화(standard real-valued optimization)와 결정적 반올림 경우에서는 나타나지 않습니다. 마지막으로, 확률적 반올림 방식(stochastic rounding schemes)에 대한 균일 인자 안정성(uniform argument stability)의 상한을 제공하고, 손실이 좌표별 함수(coordinate-wise functions)의 합으로 표현될 때 이 상한들이 타이트함(tight)을 보여줍니다.
지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백
The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference
대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.
강볼록 집합 상의 무작위화 선형 오라클 최적화에 대한 하한
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
최근 결과들[arXiv:2602.04378, arXiv:2602.22608]은 강볼록 집합 위의 최적화에 대한 하한을 각각 특정 Frank-Wolfe 갱신과 제한 없는 결정론적 1차 선형 최소화 오라클(LMO) 방법에 대해 확립하였다. 어느 쪽도 제한 없는 무작위화 방법에 대한 하한은 확립하지 못한다. 우리는 최종 출력이 모든 인스턴스와 시드에서 실현 가능해야 한다는 조건 하에, 강볼록 집합 위의 무작위화 1차 LMO 방법에 대해 오라클 호출 $T$회 후 $\Omega(L\operatorname{diam}(S)^2/T^2)$ 분포적 하한을 증명함으로써 이 간극을 메운다. 우리의 구성은 [arXiv:2602.22608]의 족을 재사용하지만, 증명은 적응적 질의 이후 숨겨진 순열의 조건부 분포를 규명하고 최적화기 분산을 제어하는 조합적 통계량의 기대 감소량에 대한 상계를 제시한다. 또한 동일한 오차 임계값이 적어도 $3/4$의 확률로 성립하며 정지 시간 꼬리 한계를 도출함을 보인다. 우리의 구성은 [arXiv:2602.22608]과 동일한 곡률-지름 결합을 사용한다. 상계 [arXiv:1406.1305]와의 비교는 이 결합을 반드시 고려해야 한다. 별도로, 규정된 느린 정확 직선 탐색 Frank-Wolfe 궤적이 충분히 작은 초기화 오차를 국소적으로 증폭할 수 있음을 보이며, 이는 반복당 대략 1비트의 추가 초기화 정확도에 해당한다. 또한 특정한 최종 느린 포락선을 만족하는 초기화는 평면 측도가 0임을 보인다.
AMUSE: 안정적 그래디언트 평가를 갖춘 Anytime Muon
AMUSE: Anytime Muon with Stable Gradient Evaluation
현대 심층 학습은 일반적으로 지정된 학습률 스케줄과 함께 AdamW에 의존하지만, 최근 연구들은 두 요소 모두에 이의를 제기한다. Schedule-Free 최적화는 반복 평균화를 통해 명시적 스케줄을 제거하고, Muon은 행렬 파라미터에 대해 모멘텀을 직교화함으로써 업데이트 기하학을 개선한다. Muon의 강력한 실증적 성능에도 불구하고, 그 근본 메커니즘은 부분적으로만 이해되고 있다. 우리는 river-valley 손실 지형을 통해 Muon을 연구한다. 여기서 유용한 학습 진행은 평탄하고 낮은 곡률의 bulk 부분공간(river)을 따라 이루어지며, 높은 곡률의 지배적 방향은 가파른 계곡 벽(valley walls)을 형성하여 진동을 유발한다. 우리는 실증적으로 Muon의 직교화가 bulk 성분을 증가시켜 river 진행을 가속하지만, 동시에 지배적 방향 노이즈를 증폭하여 진동하는 궤적을 유발함을 보인다. 이를 바탕으로, 우리는 Muon의 빠른 bulk 진행과 Schedule-Free 평균화의 안정화 효과를 통합하는 Anytime Muon with Stable Gradient Evaluation(AMUSE)를 제안한다. AMUSE는 시간에 따라 변하는 보간 계수를 사용하여, 초기에는 빠른 Muon 시퀀스 근처에서 그래디언트를 평가하여 신속한 적응을 이루고, 이후 점진적으로 안정적인 평균화된 시퀀스 쪽으로 이동하여 계곡 벽 진동을 억제한다. 그 결과 AMUSE는 학습률 스케줄이 필요 없으며 anytime 학습을 지원한다. 비전 태스크와 대규모 언어 모델 사전학습 전반에 걸쳐, AMUSE는 (Schedule-Free) AdamW 및 Muon 대비 성능-반복 파레토 프론티어를 일관되게 개선한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.