arXiv:2305.12056

Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent

제출 2023-05-20

원문 초록

Algorithmic stability is an important notion that has proven powerful for deriving generalization bounds for practical algorithms. The last decade has witnessed an increasing number of stability bounds for different algorithms applied on different classes of loss functions. While these bounds have illuminated various properties of optimization algorithms, the analysis of each case typically required a different proof technique with significantly different mathematical tools. In this study, we make a novel connection between learning theory and applied probability and introduce a unified guideline for proving Wasserstein stability bounds for stochastic optimization algorithms. We illustrate our approach on stochastic gradient descent (SGD) and we obtain time-uniform stability bounds (i.e., the bound does not increase with the number of iterations) for strongly convex losses and non-convex losses with additive noise, where we recover similar results to the prior art or extend them to more general cases by using a single proof technique. Our approach is flexible and can be generalizable to other popular optimizers, as it mainly requires developing Lyapunov functions, which are often readily available in the literature. It also illustrates that ergodicity is an important component for obtaining time-uniform bounds -- which might not be achieved for convex or non-convex losses unless additional noise is injected to the iterates. Finally, we slightly stretch our analysis technique and prove time-uniform bounds for SGD under convex and non-convex losses (without additional additive noise), which, to our knowledge, is novel.

함께 살펴볼 논문

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

arXiv:2607.22467v1cs.LG공통 태그 Stochastic Optimization, Generalization Bounds

투영 경사하강법 솔버 반복 학습의 복잡도 상한과 접근법

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와 연결한다.

arXiv:2606.19147v2stat.ML공통 태그 Stochastic Optimization, Generalization Bounds

로컬 모집단 위험 인증서에 관하여

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\)가 고정 테일러 요동, 좋은 경로 나머지, 경계면 교차를 분리한다. 선형 및 복합 인증서를 성분별로 적용하면 동일 표본 기대 로컬 탐색 및 집중 해제 규칙에 대한 끝점을 산출한다.

arXiv:2606.18306v1cs.LG공통 태그 Generalization Bounds, Learning Theory

필셔 너비: 통계적 다양체에서의 복잡도에 대한 기하학적 척도

Fisher Width: A Geometric Measure of Complexity on Statistical Manifolds

가우시안 너비(Gaussian width)는 고차원 확률론, 압축 감지, 볼록 최적화, 그리고 학습 이론에서 중심적인 기하학적 복잡도 척도입니다. 이는 집합이 무작위 방향으로 가지는 평균 범위를 정량화하여, 제약 조건 집합, 가설 클래스, 하강 원뿔의 유효 차원을 포착합니다. 그러나 이 개념은 본질적으로 유클리드적입니다. 반면 통계 모델은 피셔 정보 메트릭(Fisher information metric)에 의해 유도되는 자연스러운 리만 기하학을 가지며, 여기서 방향은 주변 유클리드 길이가 아닌 통계적 식별 가능성에 따라 조정됩니다. 우리는 통계적 다양체를 위한 가우시안 너비의 피셔 기하학적 유사체인 필셔 너비(Fisher width)를 소개합니다. 매개변수 점 $\theta$에서 필셔 너비는 유클리드 항등 연산자를 국소 메트릭 텐서(tensor) $G(\theta)^{1/2}$로 대체하여, 피셔 재조정(rescaled) 집합의 가우시안 너비를 측정합니다. 이는 결과적인 양이 국소 통계적 곡률에 민감하게 반응하고 매끄러운 재매개변화(reparameterization)에 대해 불변이 되도록 만듭니다. 우리는 필셔 너비의 기본 이론을 개발하여, 집중(concentration), 메트릭 섭동 안정성, 유클리드 기준선(baseline)과의 스펙트럴 비교 바운드를 포함한 가우시안 너비의 핵심 구조적 특징을 유지하면서도, 유클리드 척도에서는 보이지 않는 이방성 기하학적 효과를 포착함을 보여줍니다. 응용으로서, 우리는 Fisher-Lipschitz 가설 클래스에 대한 일반화 바운드를 증명하고 계산 가능한 추정량(estimators)을 제안하며, 이를 세 가지 모델 클래스에 걸쳐 MNIST에서 실증적으로 평가합니다. 필셔 너비는 통계적 다양체에 대하여, 가우시안 너비가 유클리드 볼록체에 대하여 갖는 것과 같은 역할을 합니다. 이 연구는 곡선 통계적 다양체에서의 복잡도와 학습을 연구하기 위한 기초를 마련합니다.

arXiv:2606.06934v1cs.LG공통 태그 Stochastic Optimization, Generalization Bounds

고정 소수점 매개변수에 대한 경사하강법과 확률적 경사하강법의 균일 안정성과 일반화 오차

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)을 보여줍니다.

arXiv:2606.07495v1cs.LG공통 태그 Stochastic Optimization, Learning Theory

머신러닝에서의 2차 경로 커널 보간 공식

Second-Order Path Kernel Interpolation Formulas in Machine Learning

학습 데이터가 신경망 예측을 어떻게 형성하는지 이해하는 것은 현대 학습 이론의 핵심 문제입니다. 2020년 Pedro Domingos는 결정론적 경사하강법으로 학습된 모든 모델에 대해 유효한 보간 공식을 제안했습니다. 이 공식은 모델의 예측을 최적화 경로를 따른 데이터 종속 커널의 적분으로 표현하는데, 해당 커널은 테스트 데이터와 학습 데이터에서 모델의 그래디언트를 정렬시킵니다. 이러한 1차 특성화는 배치 기반 확률적 최적화로 학습된 모델에 대해서도 여전히 유효합니다. 본 논문에서는 이러한 보간 공식의 2차 형태를 개발합니다. 우리는 주요 경로 커널 보간이 곡률 가중치가 적용된 보간 항에 의해 보완됨을 보여줍니다. 확률적 경사하강법의 경우, 예측의 곡률을 미니배치 그래디언트 노이즈의 공분산과 결합하는 추가적인 샘플링 유발 성분이 나타납니다. 또한 우리는 모멘텀이 적용된 확률적 경사하강법으로 표현을 확장하며, 여기서는 보간 구조가 유지되되 가중치가 메모리 관련 인자에 의해 수정됩니다. 더 나아가, 우리는 최종 예측에 대한 집중 추정을 확립하여 기대되는 2차 표현 주변의 변동 스케일을 식별합니다. 종합적으로, 이러한 결과들은 신경망 예측에 대한 경로 커널 해석을 정교화합니다.

토론

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