The Library
Pseudo-derandomizing learning and approximation
Tools
Oliveira, Igor C. and Santhanam, Rahul (2018) Pseudo-derandomizing learning and approximation. In: 22nd International Conference on Randomization and Computation (RANDOM), Princeton, NJ, USA, 20-22 Aug 2018. Published in: Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), 116 55:1-55:19. ISBN 9783959770699. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.55 ISSN 1868-8969.
|
PDF
WRAP-pseudo-derandomizing-learning-approximation-Oliveira-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (519Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.201...
Abstract
We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser [Eran Gat and Shafi Goldwasser, 2011]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed output with high probability. We explore pseudo-determinism in the settings of learning and approximation. Our goal is to simulate known randomized algorithms in these settings by pseudo-deterministic algorithms in a generic fashion - a goal we succinctly term pseudo-derandomization. Learning. In the setting of learning with membership queries, we first show that randomized learning algorithms can be derandomized (resp. pseudo-derandomized) under the standard hardness assumption that E (resp. BPE) requires large Boolean circuits. Thus, despite the fact that learning is an algorithmic task that requires interaction with an oracle, standard hardness assumptions suffice to (pseudo-)derandomize it. We also unconditionally pseudo-derandomize any {quasi-polynomial} time learning algorithm for polynomial size circuits on infinitely many input lengths in sub-exponential time. Next, we establish a generic connection between learning and derandomization in the reverse direction, by showing that deterministic (resp. pseudo-deterministic) learning algorithms for a concept class C imply hitting sets against C that are computable deterministically (resp. pseudo-deterministically). In particular, this suggests a new approach to constructing hitting set generators against AC^0[p] circuits by giving a deterministic learning algorithm for AC^0[p]. Approximation. Turning to approximation, we unconditionally pseudo-derandomize any poly-time randomized approximation scheme for integer-valued functions infinitely often in subexponential time over any samplable distribution on inputs. As a corollary, we get that the (0,1)-Permanent has a fully pseudo-deterministic approximation scheme running in sub-exponential time infinitely often over any samplable distribution on inputs. Finally, we {investigate} the notion of approximate canonization of Boolean circuits. We use a connection between pseudodeterministic learning and approximate canonization to show that if BPE does not have sub-exponential size circuits infinitely often, then there is a pseudo-deterministic approximate canonizer for AC^0[p] computable in quasi-polynomial time.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Approximation theory, Computational learning theory, Combinatorial optimization | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959770699 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 2018 | ||||||
Dates: |
|
||||||
Volume: | 116 | ||||||
Page Range: | 55:1-55:19 | ||||||
Article Number: | 55 | ||||||
DOI: | 10.4230/LIPIcs.APPROX-RANDOM.2018.55 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 11 November 2019 | ||||||
Date of first compliant Open Access: | 11 November 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 22nd International Conference on Randomization and Computation (RANDOM) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Princeton, NJ, USA | ||||||
Date(s) of Event: | 20-22 Aug 2018 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year