← All problems
Unverified
Direct Sums in Learning Theory
For a class , let be its -fold product, acting coordinatewise on . For classes and , write for their product. Determine the following quantities tightly.
-
For a marginal distribution on , can the fixed-marginal learning-curve bound be asymptotically improved for some ?
-
How does the uniform-convergence curve scale with and ?
-
How does the agnostic PAC learning curve scale with and ?
-
If is the minimum list size for which is list PAC learnable, what is the minimum list size for as a function of ?
-
Ask the parallel question when is the minimum list-compression size.
-
For equal to Graph, Natarajan, Littlestone, or Daniely--Shalev-Shwartz dimension, how does scale with and ?
