고정 소수점 매개변수에 대한 경사하강법과 확률적 경사하강법의 균일 안정성과 일반화 오차
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)을 보여줍니다.
원문 초록
We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generalization error of GD on convex, Lipschitz, and smooth loss functions, increasing the rate from $O(T/n)$ to $O(T/\sqrt{n})$, and establish matching lower bounds. We further prove that uniform stability of GD becomes $Ω(T)$, showing that stability-based generalization bounds are vacuous in this setting. In contrast, for the same losses, stochastic gradient descent with deterministic rounding admits nontrivial uniform stability guarantees, which differ qualitatively from the real-valued case and exhibit distinct dependencies on the number of iterations and the dimension: we prove tight bounds $O(T/n)$ for one dimension and $O(T^2/n)$ for higher dimensions. We also show that stochastic rounding can introduce generalization error that increases with the dimension; such a phenomenon is absent in standard real-valued optimization and in the deterministic rounding case. Finally, we provide upper bounds on uniform argument stability for stochastic rounding schemes and show that these bounds are tight when the loss can be represented as a sum of coordinate-wise functions.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.06934v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
정확한 미니맥스 1비트 비편향 압축: 헤비테일의 필연성과 유한 랜덤성 근사
Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation
점별 비편향(pointwise-unbiased) 1비트 압축기는 1비트만 전송하면서도 모든 실수 입력을 기댓값 상에서 복원한다. CDF가 $F$이고 평균이 $m$인 스칼라 소스 $P$와 $\mathcal J(P)=\int_{\mathbb R}\sqrt{F(r)(1-F(r))}\,dr$에 대해, 우리는 $\mathbb R$ 상에서 비편향인 모든 퍼블릭 코인(public-coin) 1비트 코드에 걸친 소스 평균 복원 2차 모멘트의 하한(infimum)이 $m^2+\mathcal J(P)^2$임을 증명한다. 정칙(regular)이며 전체 지지집합(full-support)을 갖는 소스의 경우, 분포 중심(distribution-centered) 랜덤 임계값 코드가 이 값을 달성한다. 임의의 랜덤화 이진 인코더에 대한 역(converse) 증명과 등호 분석을 통해, 영집합(null set), 비트 재라벨링, 퍼블릭 시드 세분화를 제외하고 이 값을 달성하는 모든 코드를 특성화한다. 가우시안 위치 패밀리 $\mathcal N(\mu,\sigma^2)$ ($|\mu|\le c\sigma$)의 경우, 양 끝점 평균에 대한 균등 사전분포(equal prior)가 최악의 경우(least favorable)이며 미니맥스 값은 $\sigma^2\Lambda_c^2$이다. 가우시안에서 정확한 미니맥스 최적성을 얻으려면 임계적인 헤비테일이 필요하다. 즉, 끝점 평균에서 절대 모멘트는 정확히 $p<3$일 때만 유한하며, $\Pr(W>t)=\Theta(t^{-3}/\sqrt{\log t})$이다. 코시 혼합(Cauchy-mixture) 강건화는 2차 모멘트를 최대 $1/(1-\eta)$배만 증가시키면서 모든 양의 차수 절대 모멘트를 유한하게 만든다. 유한 지지집합의 퍼블릭 랜덤성과 유한한 디코더 평균으로는 $\mathbb R$ 상에서 정확한 비편향성을 달성할 수 없지만, 정확히 $R$개의 공유 랜덤 비트를 사용하는 유계 출력(bounded-output) 근사는 미니맥스 상수로 수렴하는 명시적인 바이어스 및 2차 모멘트 경계를 갖는다. 마지막으로, 좌표 할당(coordinate allocation)은 가우시안 그래디언트 쿼리당 정확히 $B$비트를 전달한다. Kim의 연속 이차 하드 패밀리(continuous quadratic hard family)에서, 기대 최적화 보장은 $(\sigma,d,B,\varepsilon)$에 대한 의존성 측면에서 하한과 일치하며, 유한 분산 고확률 경계(high-probability bound)는 로그 수준의 신뢰도 인자만 추가로 발생시킨다.
투영 경사하강법 솔버 반복 학습의 복잡도 상한과 접근법
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와 연결한다.
검증 가능 보상 강화학습을 위한 비공허 일반화 상한
Non-vacuous Generalization Bounds for Reinforcement Learning with Verifiable Rewards
검증 가능 보상 강화학습(RLVR)은 대규모 언어 모델(LLM)의 추론 능력을 향상시키는 데 널리 사용되지만, 그렇게 얻어진 모델의 일반화 가능성은 여전히 잘 이해되지 않고 있다. 본 연구에서는 수십억 매개변수 규모에서 매개변수 효율적 RLVR 미세조정에 대한 최초의 비공허 일반화 상한을 제시한다. 우리의 접근법은 PAC-Bayes 압축 상한을 이 설정에 맞게 조정하고, Gumbel-max 재매개변수화(reparameterization) 트릭을 적용하여 토큰 생성의 고유한 확률성을 다룬다. 이 상한을 실용화하기 위해 RLVR을 온-정책 지식 증류, TinyLoRA, 모델 양자화와 통합하는 Progressive RLVR 프레임워크를 제안한다. Progressive RLVR은 경험적으로 표준 LoRA 미세조정 성능의 84–97%를 유지하면서 14,796배 더 압축 가능한 모델을 생성한다. 우리는 이 프레임워크가 수학 문제 풀이, 프로그래밍, 일반 지식 추론, Text-to-SQL 네 영역에서 비공허 일반화 상한을 제공함을 보인다. 우리의 상한은 기본 모델의 정확도를 9–51% 초과하며, 미세조정된 모델의 정확도와 6–11% 이내의 차이에 있다.
M+Adam: 가산-승산 최적화를 통한 저정밀도 학습
M+Adam: Low-Precision Training via Additive-Multiplicative Optimization
양자화된 가중치로 학습하면 비용을 절감할 수 있지만, 특히 고정밀도 복사본을 저장하지 않고 저정밀도로 최적화를 수행할 경우 정확도가 저하되는 경우가 많습니다. 우리는 핵심 실패 모드를 규명합니다: 저정밀도 환경에서 표준 옵티마이저는 특히 거친 가수부(mantissa) 해상도로 인해 큰 가중치 크기에서 정체되어 진전을 이루지 못할 수 있습니다. 이를 극복하기 위해, 표준 옵티마이저의 가산 업데이트 대신 승산 업데이트가 기존에 제안된 바 있습니다. 로그 수 체계(logarithmic number system)와 같은 극저정밀도 환경에서는 효과적이지만, 이러한 방법은 0 근방 및 부호 변환 시 실패 문제를 겪습니다. 따라서 가산 업데이트와 승산 업데이트의 실패 모드는 상호 보완적입니다. 이를 활용하기 위해, 우리는 두 가지 업데이트 유형을 결합한 M+Adam을 제안합니다: 가산 스텝은 부호 변환과 작은 크기를 처리하고, 승산 스텝은 반올림 시 가산 업데이트가 소거되는 큰 가중치 크기에서 진전을 보장합니다. 우리는 표준 평활성 가정 하에서 M+Adam의 단조 감소(monotone descent)를 증명합니다. 60M–1B 규모 모델을 사용한 LLaMA 스타일 사전학습, 1x–8x Chinchilla 예산, BF16·FP8·FP4 마스터 가중치만을 사용하는 조건 전반에서 M+Adam은 저정밀도 학습을 일관되게 개선합니다.
리퀀셜 코딩: 자가 생성 학습 데이터로 모델 압축의 한계를 넘어서
Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data
압축은 지능의 근본이다. 학습 데이터를 짧은 코드로 표현할 수 있는 모델은 일반화를 가능하게 하는 규칙성을 발견한 것이다. 대형 신경망은 매개변수 수가 시사하는 것보다 훨씬 단순한 함수를 학습할 수 있지만, 이러한 단순성을 실현하는 코드를 구성하기는 어렵다. 양자화와 같은 매개변수 기반 방법은 매개변수가 저장하는 정보량에 무관하게 모델 크기에 비례하는 코드 길이를 생성한다. 프리퀀셜 코딩(Prequential coding)은 학습 궤적을 압축함으로써 이 문제를 우회하지만, 모델이 얼마나 학습하는지와 무관하게 정확한 데이터 시퀀스를 코딩하여 데이터의 엔트로피가 높을 때 큰 코드를 생성한다. 우리는 리퀀셜 코딩(requential coding)을 소개한다. 이 방법에서는 교사 모델이 학생 모델 자신의 분포에서 추출된 학습 샘플을 선택한다. 학생의 코드는 이러한 선택만을 기록하며, 교사와 학생이 불일치하는 경우에만 비트 비용이 발생한다. 결과적인 코드 길이는 매개변수 수와 데이터 엔트로피에 무관하며, 프리퀀셜 방식보다 종종 수 자릿수 더 짧고, 스케일이 커질수록 이점이 커진다. 이러한 압축은 기존 압축기로는 접근할 수 없었던 현상들을 밝혀준다. 손실을 고정했을 때, 더 큰 모델과 앙상블은 더 많은 매개변수를 가짐에도 불구하고 훨씬 작은 크기로 압축된다. PAC-Bayes 바운드에 적용했을 때, 리퀀셜 코드는 수십억 매개변수 대규모 언어 모델(LLM)에 대해 최첨단 일반화 보장을 제공하며, 오류 없음을 가정하더라도 공격적인 사후 학습 양자화를 기반으로 한 바운드를 능가한다. 이 바운드는 컴퓨팅 최적 체제에서 스케일이 커질수록 타이트해지는데, 이는 모델이 데이터셋 크기 대비 점점 더 압축 가능해지기 때문이다. 동일한 코드는 모델이 여러 에폭에 걸쳐 학습될 때 점진적으로 과적합됨을 예측한다. 또한 데이터셋에서 학습 가능한 정보를 예측 불가능한 무작위 내용과 분리하여, 낮은 엔트로피의 텍스트가 높은 엔트로피의 이미지 데이터보다 훨씬 더 많은 학습 가능한 구조를 포함함을 밝혀낸다.
The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference
토론
이 논문과 연결된 포럼 글이 아직 없습니다.