Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of HalfspacesNearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces

Access Restriction
Subscribed

 Author De, Anindya ♦ Diakonikolas, Ilias ♦ Feldman, Vitaly ♦ Servedio, Rocco A Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Boolean function ♦ Chow parameters ♦ Fourier analysis ♦ Threshold function Abstract The Chow parameters of a Boolean function $\textit{f}:{™1,$ $1}^{n}$ → {™1, 1} are its $\textit{n}+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 [Chow 1961; Tannenbaum 1961] that the (exact values of the) Chow parameters of any linear threshold function $\textit{f}$ uniquely specify $\textit{f}$ within the space of all Boolean functions, but until recently [O'Donnell and Servedio 2011] nothing was known about efficient algorithms for $\textit{reconstructing}$ $\textit{f}$ (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem. Our main result is a new algorithm for the Chow Parameters Problem which, given (sufficiently accurate approximations to) the Chow parameters of any linear threshold function $\textit{f},$ runs in time $Õ(n^{2})$ ṡ $(1/ε)^{O(log^{2}(1/ε))}$ and with high probability outputs a representation of an LTF $\textit{f}′$ that is ε-close to $\textit{f}$ in Hamming distance. The only previous algorithm [O'Donnell and Servedio 2011] had running time $poly(\textit{n})$ ṡ $2^{2^{Õ(1/ε^{2})}}.$ As a byproduct of our approach, we show that for any linear threshold function $\textit{f}$ over {-1, $1}^{n},$ there is a linear threshold function $\textit{f}′$ which is ε-close to $\textit{f}$ and has all weights that are integers of magnitude at most √n ṡ $(1/ε)^{O(log^{2}(1/ε))}.$ This significantly improves the previous best result of Diakonikolas and Servedio [2009] which gave a $poly(\textit{n})$ ṡ $2^{Õ(1/ε^{2/3})}$ weight bound, and is close to the known lower bound of max{√n, (1/ε)Ω(log log (1/ε))} [Goldberg 2006; Servedio 2007]. Our techniques also yield improved algorithms for related problems in learning theory. In addition to being significantly stronger than previous work, our results are obtained using conceptually simpler proofs. The two main ingredients underlying our results are (1) a new structural result showing that for $\textit{f}$ any linear threshold function and $\textit{g}$ any bounded function, if the Chow parameters of $\textit{f}$ are close to the Chow parameters of $\textit{g}$ then $\textit{f}$ is close to $\textit{g};$ (2) a new boosting-like algorithm that given approximations to the Chow parameters of a linear threshold function outputs a bounded function whose Chow parameters are close to those of $\textit{f}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 2 Page Count 36 Starting Page 1 Ending Page 36

Open content in new tab

Source: ACM Digital Library