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

arXiv: https://arxiv.org/abs/2311.06690 · HTML: https://mlsanity.com/paper/2311.06690/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 43 references that are in the map.
- First posted on arXiv 11 Nov 2023.

## Builds on (most cited first, 2 of 2)

- [Distributional PAC-Learning from Nisan's Natural Proofs](https://mlsanity.com/paper/2310.03641/) (2023)
- [Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness](https://mlsanity.com/paper/1611.01190/) (2016)

## Abstract (arXiv)

(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).