Downsampling for Testing and Learning in Product Distributions
  We study distribution-free property testing and learning problems where the
unknown probability distribution is a product distribution over $\mathbb{R}^d$.
For many important classes of functions, such as intersections of halfspaces,
polynomial threshold functions, convex sets, and $k$-alternating functions, the
known algorithms either have complexity that depends on the support size of the
distribution, or are proven to work only for specific examples of product
distributions. We introduce a general method, which we call downsampling, that
resolves these issues. Downsampling uses a notion of "rectilinear isoperimetry"
for product distributions, which further strengthens the connection between
isoperimetry, testing, and learning. Using this technique, we attain new
efficient distribution-free algorithms under product distributions on
$\mathbb{R}^d$:
  1. A simpler proof for non-adaptive, one-sided monotonicity testing of
functions $[n]^d \to \{0,1\}$, and improved sample complexity for testing
monotonicity over unknown product distributions, from $O(d^7)$ [Black,
Chakrabarty, & Seshadhri, SODA 2020] to $\widetilde O(d^3)$.
  2. Polynomial-time agnostic learning algorithms for functions of a constant
number of halfspaces, and constant-degree polynomial threshold functions.
  3. An $\exp(O(d \log(dk)))$-time agnostic learning algorithm, and an
$\exp(O(d \log(dk)))$-sample tolerant tester, for functions of $k$ convex sets;
and a $2^{\widetilde O(d)}$ sample-based one-sided tester for convex sets.
  4. An $\exp(\widetilde O(k \sqrt d))$-time agnostic learning algorithm for
$k$-alternating functions, and a sample-based tolerant tester with the same
complexity.
