Oral
Sparse Polynomial Learning and Graph Sketching
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans

Wed Dec 10th 09:50 -- 10:10 AM @ Level 2, room 210
in Oral Session 5 »
Let $f: \{-1,1\}^n \rightarrow \mathbb{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 \textit{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.

Author Information

Murat Kocaoglu (MIT-IBM Watson AI Lab IBM Research, MA)
Karthikeyan Shanmugam (IBM Research)
Alex Dimakis (University of Texas, Austin)
Adam Klivans (UT Austin)

More from the Same Authors