Testing and Learning Polynomials over Reals

Abstract:

Classical algorithms are generally considered efficient if their running time is proportional to the input size. However, with the staggering amounts of data now being generated daily, even a single pass over the input may not be feasible.
Sublinear-time algorithms that are designed to provide an approximate answer based on reading only a small part of the input, solve this problem. For e.g., property testing algorithms efficiently determine with high probability if a given input, typically of large size, satisfies some property of interest, typically expressible as a subset of functions over the input space, while minimizing the part of the input that the algorithm needs to read.

In this thesis, we investigate some fundamental questions on testing and learning multivariate, real-valued functions, defined over the reals:
• We begin by designing query-efficient algorithms for testing if such a function, given via (approximate) query access, is a low degree polynomial. We also design query-optimal algorithms for the specific case of testing linearity.
• We then pivot towards testing if such functions, have some concise representation, explicitly, or implicitly, e.g., being a sparse polynomial with only a few monomials, or having only a few influential variables, i.e., a junta.
• Finally, we round up this thesis by giving sample-optimal algorithms for learning a polynomial representation for such functions, even in presence of adversarial corruptions, with strong (maximum loss) learning guarantees.