License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.37
URN: urn:nbn:de:0030-drops-117221
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11722/
Bogdanov, Andrej ;
Wang, Baoxiang
Learning and Testing Variable Partitions
Abstract
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 V into k non-empty subsets (X_1, ̇s, X_k) such that F(V) is δ-close to F_1(X_1)+ ̇s+F_k(X_k) for some F_1, ̇s, 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 O(k n^2)(δ + ε) can be learned in time Õ(n^2 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 √(δ^2 + ε) can be learned in time Õ(n^5/ε^2).
3) When F is Z_q-valued and the error metric is Hamming weight, k-partitionability is testable with one-sided error and 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.
BibTeX - Entry
@InProceedings{bogdanov_et_al:LIPIcs:2020:11722,
author = {Andrej Bogdanov and Baoxiang Wang},
title = {{Learning and Testing Variable Partitions}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {37:1--37:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11722},
URN = {urn:nbn:de:0030-drops-117221},
doi = {10.4230/LIPIcs.ITCS.2020.37},
annote = {Keywords: partitioning, agnostic learning, property testing, sublinear-time algorithms, hypergraph cut, reinforcement learning}
}
|
Keywords: |
|
partitioning, agnostic learning, property testing, sublinear-time algorithms, hypergraph cut, reinforcement learning |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
