Concentration in unbounded metric spaces and algorithmic stability
We prove an extension of McDiarmid's inequality for metric spaces with unbounded diameter. To this end, we introduce the notion of the {\em subgaussian diameter}, which is a distribution-dependent refinement of the metric diameter. Our technique provides an alternative approach to that of Kutin and Niyogi's method of weakly difference-bounded functions, and yields nontrivial, dimension-free results in some interesting cases where the former does not. As an application, we give apparently the first generalization bound in the algorithmic stability setting that holds for unbounded loss functions. We furthermore extend our concentration inequality to strongly mixing processes.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
We provide upper bounds of the expected Wasserstein distance between a probability measure and its empirical version, generalizing recent results for finite dimensional Euclidean spaces and bounded functional spaces. Suc…
Gaussian ProcessesTransportation-Inequalities, Lyapunov Stability and Sampling for Dynamical Systems on Continuous State Space
We study the concentration phenomenon for discrete-time random dynamical systems with an unbounded state space. We develop a heuristic approach towards obtaining exponential concentration inequalities for dynamical syste…
reinforcement-learningReinforcement Learning (RL)Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments
While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptio…
High-Dimensional Concentration and Retrieval Instability in Embedding Spaces: Implications for Retrieval-Augmented Generation
Embedding-based retrieval systems rely on the assumption that geometric proximity in highdimensional representation spaces reflects semantic relevance. However, high-dimensional geometry induces concentration phenomena t…
Max-sliced Wasserstein concentration and uniform ratio bounds of empirical measures on RKHS
Optimal transport and the Wasserstein distance $\mathcal{W}_p$ have recently seen a number of applications in the fields of statistics, machine learning, data science, and the physical sciences. These applications are ho…