Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds
We present new information-theoretic generalization guarantees through the a novel construction of the "neighboring-hypothesis" matrix and a new family of stability notions termed sample-conditioned hypothesis (SCH) stability. Our approach yields sharper bounds that improve upon previous information-theoretic bounds in various learning scenarios. Notably, these bounds address the limitations of existing information-theoretic bounds in the context of stochastic convex optimization (SCO) problems, as explored in the recent work by Haghifam et al. (2023).
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsSimilar Papers 제목 키워드 기반
Detection threshold for correlated Erdős-Rényi graphs via densest subgraphs
The problem of detecting edge correlation between two Erd\H{o}s-R\'enyi random graphs on $n$ unlabeled nodes can be formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are sampled indepe…
Support Tokens, Stability Margins, and a New Foundation for Robust LLMs
Self-attention is usually described as a flexible, content-adaptive way to mix a token with information from its past. We reinterpret causal self-attention transformers, the backbone of modern foundation models, within a…
Spectral Thresholds for Identifiability and Stability:Finite-Sample Phase Transitions in High-Dimensional Learning
In high-dimensional learning, models remain stable until they collapse abruptly once the sample size falls below a critical level. This instability is not algorithm-specific but a geometric mechanism: when the weakest Fi…
Condition numbers in multiview geometry, instability in relative pose estimation, and RANSAC
In this paper, we introduce a general framework for analyzing the numerical conditioning of minimal problems in multiple view geometry, using tools from computational algebra and Riemannian geometry. Special motivation c…
Pose EstimationMatching recovery threshold for correlated random graphs
For two correlated graphs which are independently sub-sampled from a common Erd\H{o}s-R\'enyi graph $\mathbf{G}(n, p)$, we wish to recover their \emph{latent} vertex matching from the observation of these two graphs \emp…