NIPS: Oral Session 5 - Alexandros G. Dimakis

438 views · Published 18 August 2016 · 20:14 · Indexed 27 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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 2s   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 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.

More from this channel