Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In theoretical machine learning, VC-dimension (VCD) and Rademacher average (RA) are two frequently used uniform bounds, providing better sample complexity than bounds such as Chernoff bound and Hoeffding bound.
Are there other uniform bounds other than VCD and RA that are tighter?
There's some confusion in the question which I'll try to clear up. First, let's dispense with "better sample complexity than bounds such as Chernoff bound and Hoeffding bound". These concentration results are invoked, implicitly or explicitly, in the VC and Rademacher bounds as well and are essentially unimprovable (unless you want to take into account variance information -- then use Bernstein [look up "fast rates"]; but I suspect that's beyond the scope of the OP).
Second, let's clarify the term "uniform bounds". Uniform typically means over a specified function class, but you also need to specify the distribution: is it fixed, or do you seek uniform bounds over distributions as well? (In the latter case, they're called "universal".) Restricting ourselves to the binary case, for uniform universal bounds, VC provides tight upper and lower bounds, and hence essentially tells the whole story -- nothing to improve here. (I'm sweeping some subtleties under the rug; see this question: Proper PAC learning VC dimension bounds .)
Now let's talk about fixed-distribution rather than universal. Now the covering numbers tell the whole story, and they also provide upper and lower bounds on Rademacher complexity. See this, quite relevant, question: Rademacher complexity beyond the agnostic setting .
tl;dr it all comes down to covering numbers
