Boolean Hypercube Fourier Analysis and Learning
Explore the concept of Fast Fourier Sparsity Testing over the Boolean Hypercube through joint research efforts, showcasing the applications of Fourier analysis in PAC-style learning and testing sparsity in Boolean functions. Learn about the connections between Fourier concentration, PAC-learning, and tolerant property testing in this domain.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Fast Fourier Sparsity Testing over the Boolean Hypercube Grigory Yaroslavtsev http://grigory.us Joint with Andrew Arnold (Waterloo), Arturs Backurs (MIT), Eric Blais (Waterloo) and Krzysztof Onak (IBM).
Fourier Analysis ?(?1, ,??): 0,1? Notation switch: 0 1 1 1 ? : 1,1? Functions as vectors form a vector space: ?: 1,1? ? 2? Inner product on functions = correlation : ?,? = 2 ? ? ? ?(?) = ?? 1,1? ? ? ? ? ? 1,1? ?? 1,1? ?2? ? 2= ?,? =
Fourier Analysis For ? [?] let character??(?) = ? ??? Fact: Every function ?: 1,1? can be uniquely represented as a multilinear polynomial ? ? ??(?) ? ?1, ,?? = ? [?] ? ? Fourier coefficient of ? on ? = ?,?? Parseval s Thm: For any ?: 1,1? ? ?? ?,? = ?? 1,1? ?2? = ? [?]
PAC-style learning PAC-learning under uniform distribution: for a class of functions ?, given access to ? ? and ? find a hypothesis ?such that ? 1,1?[? ? ?(?)] ? Query model : (?,?(?)), for any ? 1,1? Fourier analysis helps because of sparsity in Fourier spectrum Low-degree concentration Concentration on a small number of Fourier coefficients Pr
Fourier Analysis and Learning Def (Fourier Concentration): Fourier spectrum of ?: 1,1? is ?-concentrated on a collection of subsets ? ? if: ? ?2 1 ? ? ? ,? ? ? Sparse Fourier Transform [Goldreich-Levin/Kushilevitz- Mansour]:Class ?which is ?-concentrated on M sets can be PAC-learned with M ? ???? 1 ? queries: ?? 1,1? (? ?)2? ? dist ?,? = ? ? 2=
Testing Sparsity in 2 Tolerant Property Tester Property Tester Accept with probability ? k- k- Accept with probability ? sparse sparse ? ? Don t care ?-close ??-close Don t care (??,??)-close Reject with probability ? Reject with probability ? NO NO ? ? ?-close : dist(?,k-sparse)= ? k sparse????(?,?) ? inf
Previous work under Hamming Testing sparsity of Boolean functions under Hamming distance [Gopalan,O Donnell,Servedio,Shiplka,Wimmer 11 Non-tolerant test ?6 Complexity ? ?14log? + Reduction to testing under 2 Lower bound ( ?) [Yoshida, Wimmer 13] Tolerant test Complexity ???? ?,1 Our results give a tolerant test with almost quadratic improvement on [GOSSW 11] ?2log ? ?
Pairwise Independent Hashing ?,?Pr ? = ?, ? = ? = Pr ? = ? Pr[ ? = ?]
Pairwise Fourier Hashing [FGKP09] = Cosets of a random linear subspace of ?? ? = ?? Projection of ?on the coset 2= 2 "Energy" = ? ?? 2 2 ?
Testing k-sparsity [GOSSW11] # = ? ?2 log1 Fact: ? ? random samples from ?suffice 2up to ? with prob. 1 ? Algorithm: Estimate all projections up to ?2/?4with probability 1 ? ?6log ? ?4 ? to estimate ?? 2 1 ?2 Complexity: ? , only non-tolerant
Our Algorithm ? ?8 Take # cosets B = ? ? be a random sample from ?? Let ?? For a coset ?let ??= median(?? ? = ? log ? Output max ? ? , ? =? ? ??? ?, ,?? ?), where ? ?8 log? Complexity: ? Fact:The median estimators suffice to estimate all ?? 2 ? 2 up to ?
Analysis ? ?8 Take # cosets B= ? ? be a random sample from ?? Let ?? For a coset ?let ??= median(?? ? = ? log ? Output max ? ? , ? =? ? ??? ?, ,?? ?), where Two main challenges Top-k coefficients may collide Noise from non top-k coefficients
Analysis: Large coefficients ? Lemma: Fix ? = 8?. If all coefficients are ? then for ?2 buckets the weight in buckets with collisions ? Proof: # coefficients 1/? ? ? 2 ?? ? 1 Pr[coefficient ? collides] 4 By Markov w.p. 1 2 the colliding weight ? 2
Analysis: Small coefficients ? Lemma: Fix ? = 8?. If all coefficients are ? then for ?2 buckets the weight in any subset of size ? is ? Light buckets with weight 2? contribute ?/4 Heavy buckets contribute ? = ? [? ]??: Weighted # collisions W = ? ? ? ????? ? ? = ? ? ? Each ??in a heavy bucket ?? contributes ?? ? ? 2 ???? ?2 1 ? ?? 1 ? 2 2 to ? 2 Overall: ? ? ?2 ? ? 2? ? 2? ? 2
Analysis: Putting it together Lemma: If the previous two lemmas hold then the 2 ? instead of ? because of error in singleton heavy coefficients Crude bound because of pairwise independence + Cauchy-Schwarz 2-error of the algorithm is at most ? 2-error ?2 If ? = ? ?4 B = ?(?/?8) and 2
Other results + Open Problems ? ?2 log ?+ 1 ?4 non-tolerant test Our result: ? Using BLR-test to check linearity of projections Lower bound of [GOSSW 11] is ( ?) Extensions to other domains Sparse FFT on the line [Hassanieh, Indyk,Katabi,Price 12] Sparse FFT in d dimensions [Indyk, Kapralov 14] Other properties that can be tested in 2? Monotonicity, Lipschitzness, convexity [Berman, Raskhodnikova, Y. 14]
