ECCC-Report TR16-172https://eccc.weizmann.ac.il/report/2016/172Comments and Revisions published for TR16-172en-usWed, 13 Jun 2018 19:24:18 +0300
Revision 4
| Preserving Randomness for Adaptive Algorithms |
William Hoza,
Adam Klivans
https://eccc.weizmann.ac.il/report/2016/172#revision4Suppose $\mathrm{Est}$ is a randomized estimation algorithm that uses $n$ random bits and outputs values in $\mathbb{R}^d$. We show how to execute $\mathrm{Est}$ on $k$ adaptively chosen inputs using only $n + O(k \log(d + 1))$ random bits instead of the trivial $nk$ (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator (STOC '94) with a new scheme for shifting and rounding the outputs of $\mathrm{Est}$. We prove that modifying the outputs of $\mathrm{Est}$ is necessary in this setting, and furthermore, our algorithm's randomness complexity is near-optimal in the case $d \leq O(1)$. As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F: \{0, 1\}^n \to \{-1, 1\}$ using $O(n \log n) \cdot \mathrm{poly}(1/\theta)$ queries to $F$ and $O(n)$ random bits (independent of $\theta$), improving previous work by Bshouty et al. (JCSS '04).Wed, 13 Jun 2018 19:24:18 +0300https://eccc.weizmann.ac.il/report/2016/172#revision4
Revision 3
| Preserving Randomness for Adaptive Algorithms |
William Hoza,
Adam Klivans
https://eccc.weizmann.ac.il/report/2016/172#revision3Suppose $\mathrm{Est}$ is a randomized estimation algorithm that uses $n$ random bits and outputs values in $\mathbb{R}^d$. We show how to execute $\mathrm{Est}$ on $k$ adaptively chosen inputs using only $n + O(k \log(d + 1))$ random bits instead of the trivial $nk$ (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator (STOC '94) with a new scheme for shifting and rounding the outputs of $\mathrm{Est}$. We prove that modifying the outputs of $\mathrm{Est}$ is necessary in this setting, and furthermore, our algorithm's randomness complexity is near-optimal in the case $d \leq O(1)$. As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F: \{0, 1\}^n \to \{-1, 1\}$ using $O(n \log n) \cdot \mathrm{poly}(1/\theta)$ queries to $F$ and $O(n)$ random bits (independent of $\theta$), improving previous work by Bshouty et al. (JCSS '04).Thu, 02 Nov 2017 21:16:29 +0200https://eccc.weizmann.ac.il/report/2016/172#revision3
Revision 2
| Preserving Randomness for Adaptive Algorithms |
William Hoza,
Adam Klivans
https://eccc.weizmann.ac.il/report/2016/172#revision2Suppose $\mathsf{Est}$ is a randomized estimation algorithm that uses $n$ random bits and outputs values in $\mathbb{R}^d$. We show how to execute $\mathsf{Est}$ on $k$ adaptively chosen inputs using only $n + O(k \log(d + 1))$ random bits instead of the trivial $nk$ (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator (STOC '94) with a new scheme for shifting and rounding the outputs of $\mathsf{Est}$. We prove that modifying the outputs of $\mathsf{Est}$ is necessary in this setting, and furthermore, our algorithm's randomness complexity is near-optimal in the case $d \leq O(1)$. As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F: \{0, 1\}^n \to \{-1, 1\}$ using $O(n \log n) \cdot \poly(1/\theta)$ queries to $F$ and $O(n)$ random bits (independent of $\theta$), improving previous work by Bshouty et al. (JCSS '04).Tue, 11 Apr 2017 07:14:29 +0300https://eccc.weizmann.ac.il/report/2016/172#revision2
Revision 1
| Preserving Randomness for Adaptive Algorithms |
William Hoza,
Adam Klivans
https://eccc.weizmann.ac.il/report/2016/172#revision1We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is allowed to modify the output of $\mathrm{Est}$. The notion of a steward is inspired by adaptive data analysis, introduced by Dwork et al. (STOC '15). Suppose $\mathrm{Est}$ outputs values in $\R^d$, has $\ell_{\infty}$ error $\epsilon$, has failure probability $\delta$, uses $n$ coins, and will be executed $k$ times. For any $\gamma > 0$, we construct a computationally efficient steward with $\ell_{\infty}$ error $O(\epsilon d)$, failure probability $k \delta + \gamma$, and randomness complexity $n + O(k \log(d + 1) + (\log k) \log(1/\gamma))$. To achieve these parameters, the steward uses a pseudorandom generator for what we call the block decision tree model, combined with a scheme for shifting and rounding the outputs of $\mathrm{Est}$. The generator is a variant of the INW generator (STOC '94) for space-bounded computation. We also give variant stewards that achieve tradeoffs in parameters.
As an application of our steward, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F: \{0, 1\}^n \to \{-1, 1\}$ using $O(n \log n) \cdot \mathrm{poly}(1/\theta)$ queries to $F$ and $O(n)$ random bits (independent of $\theta$), improving previous work by Bshouty et al. (JCSS '04). We also give time- and randomness-efficient algorithms for estimating the acceptance probabilities of many adaptively chosen Boolean circuits and for simulating any algorithm with an oracle for $\mathrm{promise\mbox{-}BPP}$ or $\mathrm{APP}$.
We prove that nontrivial pseudorandom generators for this setting do not exist, i.e. modifying the outputs of $\mathrm{Est}$ is necessary. We also prove a randomness complexity lower bound of $n + \Omega(k) - \log(\delta'/\delta)$ for any "one-query steward" with failure probability $\delta'$, which nearly matches our upper bounds in the case $d \leq O(1)$.Thu, 16 Feb 2017 04:08:21 +0200https://eccc.weizmann.ac.il/report/2016/172#revision1
Paper TR16-172
| Preserving Randomness for Adaptive Algorithms |
William Hoza,
Adam Klivans
https://eccc.weizmann.ac.il/report/2016/172We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is allowed to modify the output of $\mathrm{Est}$. The notion of a steward is inspired by adaptive data analysis, introduced by Dwork et al. Suppose $\mathrm{Est}$ outputs values in $\mathbb{R}^d$, has $\ell_{\infty}$ error $\epsilon$, has failure probability $\delta$, uses $n$ coins, and will be executed $k$ times. For any $\gamma > 0$, we construct a computationally efficient steward with $\ell_{\infty}$ error $O(\epsilon d)$, failure probability $k \delta + \gamma$, and randomness complexity $n + O(k \log(d + 1) + (\log k) \log(1/\gamma))$. To achieve these parameters, the steward uses a pseudorandom generator for what we call the block decision tree model, combined with a scheme for shifting and rounding the outputs of $\mathrm{Est}$. (The generator is a variant of the INW generator for space-bounded computation.) We also give variant stewards that achieve tradeoffs in parameters.
As applications of our steward, we give time- and randomness-efficient algorithms for estimating the acceptance probabilities of many adaptively chosen Boolean circuits and for simulating any algorithm with an oracle for $\mathrm{promise\mbox{-}BPP}$ or $\mathrm{APP}$. We also give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F: \{0, 1\}^n \to \{-1, 1\}$ using $O(n \log n) \cdot \mathrm{poly}(1/\theta)$ queries to $F$ and $O(n)$ random bits, improving previous work by Bshouty et al. Finally, we prove a randomness complexity lower bound of $n + \Omega(k) - \log(\delta'/\delta)$ for any steward with failure probability $\delta'$, which nearly matches our upper bounds in the case $d \leq O(1)$.Fri, 04 Nov 2016 10:17:53 +0200https://eccc.weizmann.ac.il/report/2016/172