Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques

(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 2n. 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 2n -s(n) for s(n) ≈ n/(k+1), and learns over the uniform distribution over unlabelled examples on 0,1n. 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 2n-s(n) for s(n) ≈ n/(k+1), and learns over distributions of unlabelled examples that are products of k+1 arbitrary and unknown distributions, each over 0,1n/(k+1) (assume without loss of generality that k+1 divides n).