论文标题
小点和阈值尺寸的接近闭合边界
Near-tight closure bounds for Littlestone and threshold dimensions
论文作者
论文摘要
我们研究了二元假设类别的littlestone和阈值维度的闭合性能。 Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of Boolean functions with bounded Littlestone (respectively, threshold) dimension, we establish an upper bound on the Littlestone (respectively, threshold) dimension of the class defined by applying an arbitrary binary aggregation rule to $\mathcal{H}_1, \ ldots，\ Mathcal {H} _K $。我们还表明，我们的上限几乎很紧。我们的上限对Alon等人显示的类似边界进行了指数级（以$ K $为单位）。 （柯尔特2020），因此回答了他们的工作提出的问题。
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of Boolean functions with bounded Littlestone (respectively, threshold) dimension, we establish an upper bound on the Littlestone (respectively, threshold) dimension of the class defined by applying an arbitrary binary aggregation rule to $\mathcal{H}_1, \ldots, \mathcal{H}_k$. We also show that our upper bounds are nearly tight. Our upper bounds give an exponential (in $k$) improvement upon analogous bounds shown by Alon et al. (COLT 2020), thus answering a question posed by their work.
