Sparse Polynomial Learning and Graph Sketching
Let f : {−1, 1} n → R be a polynomial with at most s non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distribution on {−1, 1} n that runs in time polynomial in n and 2 s and succeeds if the function satisfies the unique sign property: there is one output value which corresponds to a unique set of values of the participating parities. This sufficient condition is satisfied when every coefficient of f is perturbed by a small random noise, or satisfied with high probability when s parity functions are chosen randomly or when all the coefficients are positive. Learning sparse polynomials over the Boolean domain in time polynomial in n and 2 s is considered notoriously hard in the worst-case. Our result shows that the problem is tractable for almost all sparse polynomials.
Then, we show an application of this result to hypergraph sketching which is the problem of learning a sparse (both in the number of hyperedges and the size of the hyperedges) hypergraph from uniformly drawn random cuts. We also provide experimental results on a real world dataset.
The paper describes an algorithm for learning sparse polynomials over the boolean domain. It differs from works like [12,13] in that even though it has the same sample-complexity, it has much better run-time. It uses standard l1 minimization techniques but is able to perform a "feature-selection" step to reduce the combinatorial number of subsets from 2^n to 2^s, where s is the sparsity of the polynomial.Of all the 5 other paper I reviewed for NIPS, this was the best one. However, it was also the slowest for me to read and I am the least certain about it, mainly because it was the paper farthest from my own specialty. There were quite a few arguments that I couldn't check in detail and instead rely on trusting the authors.The writing was clear, and the intuition was normally laid out well. I was at first disappointed that Lemma 2 and Theorem 4 were relegated to the appendix, but the appendix was short and I think this was OK.Overall, assuming I didn't misinterpret anything, I'm enthusiastic about publishing this paper. There was more in this paper than in most of the other papers I reviewed combined. I am a bit confused why this paper is in NIPS and not STOC, though.My minor criticisms are below:- In the abstract, the description of the unique sign property was confusing, even after reading the definition in the paper. The definitions in the paper seemed good, but not the one in the abstract.- I didn't notice the sample complexity mentioned in the first part of the paper. It is O(n), right? Please state this earlier, since it is of great interest (if it was 2^s, then a fast time complexity is sort of irrelevant)- Theorem 2: parity functions are not yet defined, so this is not yet clear to a non-expert like myself. Similarly, section 2 was a good first-step, but I still needed to supplement this with some basic notes about Fourier expansion of boolean functions.- Section 1.1. The difference in the results with [12,13] and [15] was made quite clear, but the difference in techniques was not. I am very curious how much of the technique was novel. Please state the key technical innovation (or was the main innovation just the discovery of the algorithm/idea, and then the analysis was standard?).- Section 3 and later on, the notation for an ordered pair of samples and labels uses angular brackets, which are usually reserved for inner products. Why not just use parenthesis?- Theorem 3 and following paragraph refer to feasible "solutions" of the problem, which is confusing since I interpret "solution" and "optimum" identically, and with this interpretation it makes no sense. I would say a "feasible point", not a "feasible solution".- The technique reminds me of "Safe feature elimination" by El Ghaoui, who proves a similar reduction technique for l1 minimization (in the standard compressed sensing context), but of course quite different since his variables are not linked the same way yours are.- The step of finding feasible solutions p in equation 4 in Algo 1 is not explained in the main text, so this is a bit of a mystery. It would be nice to give more intuition here. (Here, it is OK to call p a "solution" since you are just solving an equation, not solving an equation AND minimizing).- Section 5 was either written by a different co-author or not proof-read to the same degree, because the writing quality deteriorates and there are many English mistakes. Bottom of page 5, "previously" is used twice in a sentence.  There are many missing "the"'s in the sentences.- After equation 6, what is "d"?- Theorem 5 and this specialization is quite nice. However, it felt secondary so I did not check the corresponding section in the appendix (except to note that the proof of Thm 5 is hard to follow and condensed into 1 giant paragraph, very unlike the proof of Thm 4 and the lemma).- 5.2, the dataset was described, but it was never said what exactly it is (for people not familiar with Yahoo! Messenger). Is this an instant messaging, or something else? It wasn't clear to me the connection between instant messaging and zip codes, and I think you could explain this in 1 or 2 sentences to clear it all up.- In 5.2.1, you mention identifying the relevant variables correctly, but how do you know this? Was there a ground-truth solution? Did I miss something here?- The references should capitalize "Fourier" in the titles of papers.