A Smoothed Analysis for Learning Sparse Polynomials

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

Abstract

Let $f: \{-1,1\}^n \to \mathbb{R}$ be a polynomial with at most $s$ non-zero real coefficients. We present an algorithm for exactly reconstructing $f$ from random examples under the uniform distribution. The algorithm runs in time polynomial in $n$ and $2^s$, succeeding if the function satisfies the "unique sign property." This property is shown to be satisfied under smoothed analysis (small random perturbations of coefficients) or when coefficients are positive, as in hypergraph sketching. This result demonstrates that learning sparse polynomials, a notoriously hard problem in the worst-case, is tractable for almost all instances.

Introduction

Learning an unknown $s$-sparse polynomial over the Boolean hypercube $\{-1, 1\}^n$ from random examples is a fundamental challenge in computational learning theory. Historically, this task has required either active query access or exponential time in $n$. For instance, standard compressed sensing (CS) approaches require a measurement matrix with $2^n$ columns—one for every possible monomial—making them computationally infeasible for large $n$. This paper investigates whether "almost all" sparse polynomials can be learned efficiently by moving from worst-case analysis to smoothed analysis.

The LearnBool Algorithm

The authors propose LearnBool, a two-stage algorithm that leverages the unique sign property. A function satisfies this property if its maximum output value corresponds to a unique sign pattern among its participating parity functions.

  1. Candidate Pruning: The algorithm identifies the maximum observed output values from random samples. By analyzing the input vectors that produce these maximums, it solves a linear system over $\mathbb{F}_2$ to isolate a candidate set of potentially non-zero parities of size $O(2^s)$, effectively bypassing the $2^n$ bottleneck.
  2. Reconstruction: Standard $L_1$-minimization is then applied to this drastically reduced candidate set to recover the exact coefficients.

Hypergraph Sketching and Real-World Data

A key application is hypergraph sketching: inferring the structure of a sparse hypergraph from random cuts. The complement of a cut function is a sparse polynomial with positive coefficients, which inherently satisfies the unique sign property. The authors developed LearnGraph, an optimized variant for this task, and tested it on the Yahoo! Messenger User Communication Pattern dataset, which tracks user interactions over 28 days.

Experimental Results

Runtime comparison of LearnGraph vs. standard compressed sensing. Source, p. 7

Runtime comparison of LearnGraph vs. standard compressed sensing.

As shown in the runtime analysis above, LearnGraph maintains a nearly constant, low runtime as the number of variables $n$ increases. In contrast, standard compressed sensing scales exponentially. For a graph with $n=1399$ nodes, LearnGraph recovered the structure in approximately 5 seconds, while standard CS approaches either timed out or exceeded memory limits.

Error probability as a function of sample size ratio $\alpha = \text{samples}/n$.

The algorithm's reliability was tested across various settings. While the error probability decreases as the number of samples increases (represented by $\alpha$), the authors note that their method generally requires a higher sample complexity than pure compressed sensing to achieve the same error rate.

Conclusion

By exploiting structural information leaked by maximum output values, the proposed framework makes learning sparse Boolean functions tractable for practical applications. While the $2^s$ dependence limits the algorithm to high sparsity, it offers a significant breakthrough for hypergraph inference and other domains where $n$ is large but the underlying structure is sparse.

Summary updated

Abstract

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