Logarithmic aggregation conjecture for fat-shattering dimension

Let Ω\Omega be a domain, let FiRΩF_i\subseteq\mathbb{R}^{\Omega} for i[k]i\in[k], and let FmaxF_{\max} be their kk-fold maximum. Logarithmic aggregation conjecture. For some universal constant c>0c>0, for every γ>0\gamma>0,

fatγ(Fmax)cLog(k)j=1kfatγ(Fi).\operatorname{fat}_{\gamma}(F_{\max})\le c\operatorname{Log}(k)\sum_{j=1}^k\operatorname{fat}_{\gamma}(F_i).

This conjecture would give a general logarithmic-in-kk upper bound for the fat-shattering dimension of maxima of function classes. The supplied text gives matching results for particular affine classes, but does not state a resolution of this general claim.

Sources & referencesView supporting material

Primary source

Idan Attias and Aryeh Kontorovich, “Fat-Shattering Dimension of k-fold Aggregations”, arXiv:2110.04763 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.