← All problems
Unverified

Direct Sums in Learning Theory

For a class C⊆YXC\subseteq Y^X, let CrC^r be its rr-fold product, acting coordinatewise on XrX^r. For classes C1⊆Y1X1C_1\subseteq Y_1^{X_1} and C2⊆Y2X2C_2\subseteq Y_2^{X_2}, write C1⊗C2C_1\otimes C_2 for their product. Determine the following quantities tightly.

  1. For a marginal distribution DD on XX, can the fixed-marginal learning-curve bound ε(n∣Dr,Cr)≤rε(n∣D,C)\varepsilon(n\mid D^r,C^r)\leq r\varepsilon(n\mid D,C) be asymptotically improved for some C,DC,D?

  2. How does the uniform-convergence curve εUC(n∣Cr)\varepsilon_{\rm UC}(n\mid C^r) scale with εUC(n∣C)\varepsilon_{\rm UC}(n\mid C) and rr?

  3. How does the agnostic PAC learning curve εagn(n∣Cr)\varepsilon_{\rm agn}(n\mid C^r) scale with εagn(n∣C)\varepsilon_{\rm agn}(n\mid C) and rr?

  4. If kik_i is the minimum list size for which CiC_i is list PAC learnable, what is the minimum list size for C1⊗C2C_1\otimes C_2 as a function of k1,k2k_1,k_2?

  5. Ask the parallel question when kik_i is the minimum list-compression size.

  6. For dim⁡\dim equal to Graph, Natarajan, Littlestone, or Daniely--Shalev-Shwartz dimension, how does dim⁡(F⊗G)\dim(F\otimes G) scale with dim⁡(F)\dim(F) and dim⁡(G)\dim(G)?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu