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