Sparse Polynomial Learning and Graph Sketching

Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G. Dimakis, Adam R. Klivans

TL;DR

This paper presents a novel algorithm for efficiently learning sparse polynomials from random examples, a problem previously considered intractable in the worst-case. The key breakthrough lies in identifying a "unique sign property" that allows for efficient learning under natural conditions like random noise or positive coefficients, and this is applied to the problem of hypergraph sketching.

What Problem Does This Paper Address?

The core problem tackled is learning sparse polynomials from random data. Imagine a function that can be represented by a polynomial, but only a few terms (coefficients) are non-zero. Learning such functions is crucial in many areas of machine learning and computer science. The challenge is that finding these sparse polynomials from random samples, especially over the Boolean domain (where inputs are either -1 or 1), is notoriously difficult. Existing methods often require exponentially many samples or have runtimes that grow exponentially with the number of non-zero coefficients, making them impractical for even moderately sized problems. This paper aims to bridge this gap by providing an algorithm that is efficient in terms of both sample complexity and runtime for a significant class of sparse polynomials.

Methods

The paper introduces a new algorithm, "LearnBool," that leverages a crucial property called the "unique sign property." This property states that a specific output value of the polynomial uniquely determines the signs of the underlying parity functions (the building blocks of the polynomial). If this property holds, the algorithm can efficiently identify the relevant parity functions.

The algorithm works in two main stages:

  1. Identifying Relevant Parities: It first uses a clever technique to narrow down the potentially relevant parity functions from the vast $2^n$ possibilities to a much smaller set of size $O(2^s)$. This is achieved by focusing on samples that yield the maximum observed function value.
  2. Learning the Polynomial: Once this reduced set of parities is identified, the paper utilizes techniques from compressed sensing (specifically, convex optimization) to recover the sparse polynomial's coefficients.

The paper also extends these ideas to handle noisy observations and applies them to the problem of hypergraph sketching. For hypergraph sketching, they show that the "cut complement" function naturally satisfies the unique sign property, enabling efficient learning of hypergraph structures.

Datasets

The paper uses the Yahoo! Messenger User Communication Pattern Dataset for experimental evaluation. This dataset contains timestamped user communication data, including sender/receiver IDs and zip codes. The authors construct hypergraphs from this data to represent user interactions and then apply their hypergraph sketching algorithm.

Key Insights and Ideas

  • The "Unique Sign Property" is Key: This property is the central insight. It transforms a seemingly intractable problem into a tractable one by providing a way to efficiently filter down the search space for relevant polynomial terms.
  • Bridging Theory and Practice: The paper demonstrates that theoretical advancements in learning sparse polynomials can have direct applications in practical problems like hypergraph sketching, which is relevant for understanding evolving networks.
  • "Almost All" Sparse Polynomials are Learnable: While worst-case scenarios remain hard, the paper shows that under natural conditions (like random noise or positive coefficients), sparse polynomials are efficiently learnable. This is a significant theoretical result with practical implications.
  • Hypergraph Sketching as a Sparse Polynomial Problem: The paper elegantly frames hypergraph sketching as a problem of learning a sparse polynomial, allowing them to leverage their learning algorithm for this application.

Key Results

  • Efficient Sparse Polynomial Learning: The proposed algorithm learns an $s$-sparse polynomial in time polynomial in $n$ (the dimension) and $2^s$ (exponential in sparsity, but much better than $2^n$), provided the unique sign property holds.
  • Noisy Learning: An extension of the algorithm can learn approximately $s$-sparse polynomials from noisy data with bounded error.
  • Hypergraph Sketching Application: The algorithm is applied to hypergraph sketching, demonstrating a significant improvement in runtime compared to previous compressed sensing approaches, especially for larger graphs. Experimental results on the Yahoo! Messenger dataset show the algorithm scales well.
  • Theoretical Guarantees: The paper provides theoretical guarantees for both noiseless and noisy learning scenarios, showing high probability of success.

Limitations and Future Work

  • Dependence on Unique Sign Property: The efficiency of the algorithm hinges on the unique sign property. While this property holds under several natural conditions, it might not hold for all sparse polynomials.
  • Computational Complexity: While the algorithm is polynomial in $n$ and $2^s$, the $2^s$ factor can still be prohibitive if the sparsity $s$ is large.
  • Open Problem: The authors highlight an open problem: achieving the sample complexity of prior work [12] while maintaining polynomial computational complexity.
  • Future Work: The paper suggests exploring better bounds for hypergraph sketching in terms of the largest connected component rather than the total number of relevant variables. Further research into achieving better sample complexity for sparse polynomial learning is also a promising direction.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kocaoglu2014sparse,
  author = {Murat Kocaoglu and Karthikeyan Shanmugam and Alexandros G. Dimakis and Adam R. Klivans},
  title = {{Sparse Polynomial Learning and Graph Sketching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  doi = {10.48550/arxiv.1402.3902},
}
Figure