<p>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).</p>

<p>Second, let's clarify the term "uniform bounds". <em>Uniform</em> 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:
<a href="https://cstheory.stackexchange.com/questions/40161/proper-pac-learning-vc-dimension-bounds">Proper PAC learning VC dimension bounds</a>
.)</p>

<p>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:
<a href="https://cstheory.stackexchange.com/questions/40312/rademacher-complexity-beyond-the-agnostic-setting">Rademacher complexity beyond the agnostic setting</a>
.</p>

<p>tl;dr it all comes down to covering numbers</p>

CC BY-SA 3.0
2018-03-07T09:04:31.650Z
2018-03-07T09:04:31.650Z
Aryeh
<p>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. </p>

<blockquote>
  <p>Are there other uniform bounds other than VCD and RA that are tighter?</p>
</blockquote>

<machine-learning><pr.probability><vc-dimension>
Other Uniform Bound
Matteo
# Other Uniform Bound

(Asked by: username_0 on 2018-03-07)

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?

**Tags:** machine-learning, pr.probability, vc-dimension


---

## 1 answers

### Answer by username_1 on 2018-03-07. Score: 2 | Accepted answer

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](https://cstheory.stackexchange.com/questions/40161/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](https://cstheory.stackexchange.com/questions/40312/rademacher-complexity-beyond-the-agnostic-setting)
.

tl;dr it all comes down to covering numbers


---

