Generalization Bounds for Gradient Methods via Discrete and Continuous Prior
원문 초록
Proving algorithm-dependent generalization error bounds for gradient-type optimization methods has attracted significant attention recently in learning theory. However, most existing trajectory-based analyses require either restrictive assumptions on the learning rate (e.g., fast decreasing learning rate), or continuous injected noise (such as the Gaussian noise in Langevin dynamics). In this paper, we introduce a new discrete data-dependent prior to the PAC-Bayesian framework, and prove a high probability generalization bound of order $O(\frac{1}{n}\cdot \sum_{t=1}^T(\gamma_t/\varepsilon_t)^2\left\|{\mathbf{g}_t}\right\|^2)$ for Floored GD (i.e. a version of gradient descent with precision level $\varepsilon_t$), where $n$ is the number of training samples, $\gamma_t$ is the learning rate at step $t$, $\mathbf{g}_t$ is roughly the difference of the gradient computed using all samples and that using only prior samples. $\left\|{\mathbf{g}_t}\right\|$ is upper bounded by and and typical much smaller than the gradient norm $\left\|{\nabla f(W_t)}\right\|$. We remark that our bound holds for nonconvex and nonsmooth scenarios. Moreover, our theoretical results provide numerically favorable upper bounds of testing errors (e.g., $0.037$ on MNIST). Using a similar technique, we can also obtain new generalization bounds for certain variants of SGD. Furthermore, we study the generalization bounds for gradient Langevin Dynamics (GLD). Using the same framework with a carefully constructed continuous prior, we show a new high probability generalization bound of order $O(\frac{1}{n} + \frac{L^2}{n^2}\sum_{t=1}^T(\gamma_t/\sigma_t)^2)$ for GLD. The new $1/n^2$ rate is due to the concentration of the difference between the gradient of training samples and that of the prior.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
On the Limitations of Fractal Dimension as a Measure of Generalization
필셔 너비: 통계적 다양체에서의 복잡도에 대한 기하학적 척도
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에서 실증적으로 평가합니다. 필셔 너비는 통계적 다양체에 대하여, 가우시안 너비가 유클리드 볼록체에 대하여 갖는 것과 같은 역할을 합니다. 이 연구는 곡선 통계적 다양체에서의 복잡도와 학습을 연구하기 위한 기초를 마련합니다.
Generalization Bounds in Hybrid Quantum-Classical Machine Learning Models
Scaling Law for Stochastic Gradient Descent in Quadratically Parameterized Linear Regression
Stability and Generalization of Quantum Neural Networks
Data-Dependent Generalization Bounds for Parameterized Quantum Models Under Noise
토론
이 논문과 연결된 포럼 글이 아직 없습니다.