# Approximate resilience, monotonicity, and the complexity of agnostic learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2014.

## Built on by (most cited first, 16 of 16)

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions](https://mlsanity.com/paper/2502.05073/) (2025)
- [A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.07244/) (2025)
- [New Distinguishers for Negation-Limited Weak Pseudorandom Functions](https://mlsanity.com/paper/2203.12246/) (2022)
- [Faster Algorithms for Agnostically Learning Disjunctions and their Implications](https://mlsanity.com/paper/2504.15244/) (2025)
- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)
- [Efficient Robust Learning at the Information-Theoretic Limit](https://mlsanity.com/paper/2609.17655/) (2026)

## Abstract (arXiv)

A function f is d-resilient if all its Fourier coefficients of degree at most d are zero, i.e., f is uncorrelated with all low-degree parities. We study the notion of mathitapproximate mathitresilience of Boolean functions, where we say that f is α-approximately d-resilient if f is α-close to a [-1,1]-valued d-resilient function in ℓ1 distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class C over the uniform distribution. Roughly speaking, if all functions in a class C are far from being d-resilient then C can be learned agnostically in time nO(d) and conversely, if C contains a function close to being d-resilient then agnostic learning of C in the statistical query (SQ) framework of Kearns has complexity of at least nOmega(d). This characterization is based on the duality between ℓ1 approximation by degree-d polynomials and approximate d-resilience that we establish. In particular, it implies that ℓ1 approximation by low-degree polynomials, known to be sufficient for agnostic learning over product distributions, is in fact necessary. Focusing on monotone Boolean functions, we exhibit the existence of near-optimal α-approximately widetildeOmega(α√n)-resilient monotone functions for all α>0. Prior to our work, it was conceivable even that every monotone function is Omega(1)-far from any 1-resilient function. Furthermore, we construct simple, explicit monotone functions based on sf Tribes and sf CycleRun that are close to highly resilient functions. Our constructions are based on a fairly general resilience analysis and amplification. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas.