论文标题
学习和测试变量分区
Learning and Testing Variable Partitions
论文作者
论文摘要
$ $ $ $ f $是从产品集$σ^n $到Abelian Group $ g $的多元功能。 $ k $ - 分区的$ f $，成本$δ$是变量集$ \ mathbf {v} $的分区，以$ k $ nontempty子集$（\ Mathbf {x} _1，\ dots，\ dots，\ dots，\ mathbf {x} _k）$ f（x} $ f（x} $ f（mathbf） $ f_1（\ Mathbf {x} _1）+\ dots+f_k（\ Mathbf {x} _K）$对于某些$ f_1，\ dots，f_k $，相对于给定的错误度量。我们研究了不可知的算法，以学习$ k $分区和测试$ k $ - 分类性的各个组和错误指标，并给出了对$ f $的查询访问权限。特别是我们表明 $ 1. $给定一个具有$ k $ - 成本$δ$的函数，可以在时间$ \ tilde {\ tilde {\ mathcal {o}}}（n^2 \ mathrm {poly} $ $ $ $ $ $ $ $ $上），可以在时间$ \ tilde {\ mathcal {o}}（$ $）上学习成本$ \ nathcal {o}（k n^2）（k n^2）（Δ+ε）$的分区。相比之下，$ k = 2 $和$ n = 3 $学习成本$δ+ε$的分区为np-hard。 $ 2. $ $ f $是真实价值的，并且错误度量是2-norm时，可以在时间$ \ tilde {\ mathcal {o}}（n^5/ε^2）$中学习2个成本$ \ sqrt {δ^2 +ε} $。 $ 3. $ F $是$ \ Mathbb {z} _q $ - 值，并且错误度量为锤式重量时，$ k $ - 分类性是可以通过单方面错误和$ \ MATHCAL {O}（kn^3/ε）$非适应性查询来测试的。我们还表明，当$ k = 2 $时，即使是双面测试仪也需要$ω（n）$ QUERIES。 这项工作是由强化学习控制任务激发的，其中可以分区控制变量。分区将任务减少为多个较低维度的任务，这些维度相对容易学习。从经验上讲，我们的第二种算法增加了在这种情况下应用的先前启发式分区方法的得分。
$ $Let $F$ be a multivariate function from a product set $Σ^n$ to an Abelian group $G$. A $k$-partition of $F$ with cost $δ$ is a partition of the set of variables $\mathbf{V}$ into $k$ non-empty subsets $(\mathbf{X}_1, \dots, \mathbf{X}_k)$ such that $F(\mathbf{V})$ is $δ$-close to $F_1(\mathbf{X}_1)+\dots+F_k(\mathbf{X}_k)$ for some $F_1, \dots, F_k$ with respect to a given error metric. We study algorithms for agnostically learning $k$ partitions and testing $k$-partitionability over various groups and error metrics given query access to $F$. In particular we show that $1.$ Given a function that has a $k$-partition of cost $δ$, a partition of cost $\mathcal{O}(k n^2)(δ+ ε)$ can be learned in time $\tilde{\mathcal{O}}(n^2 \mathrm{poly} (1/ε))$ for any $ε> 0$. In contrast, for $k = 2$ and $n = 3$ learning a partition of cost $δ+ ε$ is NP-hard. $2.$ When $F$ is real-valued and the error metric is the 2-norm, a 2-partition of cost $\sqrt{δ^2 + ε}$ can be learned in time $\tilde{\mathcal{O}}(n^5/ε^2)$. $3.$ When $F$ is $\mathbb{Z}_q$-valued and the error metric is Hamming weight, $k$-partitionability is testable with one-sided error and $\mathcal{O}(kn^3/ε)$ non-adaptive queries. We also show that even two-sided testers require $Ω(n)$ queries when $k = 2$. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.
