Abstract

 Let  be an n-variate polynomial consisting of monomials, in which only coefficients are non-zero. The goal is to learn the polynomial by querying the values of f . We introduce an active learning framework that is associated with a low query cost and computational runtime. The significant savings are enabled by leveraging sampling strategies based on modern coding theory, specifically, the design and analysis of sparse-graph codes, such as Low-Density-Parity-Check (LDPC) codes, which represent the state-of-the-art of modern packet communications. More significantly, we show how this design perspective leads to exciting, and to the best of our knowledge, largely unexplored intellectual connections between learning and coding. The key is to relax the worst-case assumption with an ensemble-average setting, where the polynomial is assumed to be drawn uniformly at random from the ensemble of all polynomials (of a given size n and sparsity s). Our framework succeeds with high probability with respect to the polynomial ensemble with sparsity up to (0, 1), where f is exactly learned using O(ns) queries in time O(ns log s), even if the queries are perturbed by Gaussian noise. We further apply the proposed framework to graph sketching, which is the problem of inferring sparse graphs by querying graph cuts. By writing the cut function as a polynomial and exploiting the graph structure, we propose a sketching algorithm to learn the an arbitrary n-node unknown graph using only few cut queries, which scales almost linearly in the number of edges and sub-linearly in the graph size n. Experiments on real datasets show significant reductions in the runtime and query complexity compared with competitive schemes.