Agnostic Membership Query Learning with Nontrivial Savings: New Results,
  Techniques
Ari Karchmer
(Abridged) Designing computationally efficient algorithms in the agnostic
learning model (Haussler, 1992; Kearns et al., 1994) is notoriously difficult.
In this work, we consider agnostic learning with membership queries for
touchstone classes at the frontier of agnostic learning, with a focus on how
much computation can be saved over the trivial runtime of 2^n$. This approach
is inspired by and continues the study of ``learning with nontrivial savings''
(Servedio and Tan, 2017). To this end, we establish multiple agnostic learning
algorithms, highlighted by:
  1. An agnostic learning algorithm for circuits consisting of a sublinear
number of gates, which can each be any function computable by a sublogarithmic
degree k polynomial threshold function (the depth of the circuit is bounded
only by size). This algorithm runs in time 2^{n -s(n)} for s(n) \approx
n/(k+1), and learns over the uniform distribution over unlabelled examples on
\{0,1\}^n.
  2. An agnostic learning algorithm for circuits consisting of a sublinear
number of gates, where each can be any function computable by a \sym^+ circuit
of subexponential size and sublogarithmic degree k. This algorithm runs in time
2^{n-s(n)} for s(n) \approx n/(k+1), and learns over distributions of
unlabelled examples that are products of k+1 arbitrary and unknown
distributions, each over \{0,1\}^{n/(k+1)} (assume without loss of generality
that k+1 divides n).