Sparse Polynomial Learning and Graph Sketching
This addresses a notoriously hard problem in computational learning theory for sparse polynomials, with implications for graph and hypergraph analysis, though it is incremental as it relies on a specific property rather than solving the worst-case scenario.
The paper tackles the problem of exactly reconstructing sparse polynomials over Boolean domains from random examples, showing it is tractable for almost all such polynomials under a unique sign property, with an algorithm running in time polynomial in n and 2^s. It applies this result to hypergraph sketching, providing experimental validation on real-world data.
Let $f:\{-1,1\}^n$ 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 $2s$ 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 $2s$ 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.