A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity

Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin
9/24/2025
stat.MLcs.LGmath.ST

No confident code implementation found for this paper.

Abstract

We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class are controlled above by these gapped dimensions, generalizing the results of \cite{anthony2000function,alon1997scale}. Moreover, we show that the gapped dimensions lead to lower bounds on offset Rademacher averages, thereby strengthening existing approaches for proving lower bounds on rates of convergence in statistical and online learning.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions

82% match2023

Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

80% match1 repo232025

Generalization Guarantees via Algorithm-dependent Rademacher Complexity

79% match2023

Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization

79% match2024

Lean Formalization of Generalization Error Bound by Rademacher Complexity

79% match1 repo232025

The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms

77% match2026

Cite this paper

@article{jia2025gapped,
  title  = {A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity},
  author = {Zeyu Jia and Yury Polyanskiy and Alexander Rakhlin},
  year   = {2025},
  eprint = {2509.20618},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2509.20618v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2509.20618.svg)](https://codeofpaper.com/paper/2509.20618)

Discussion