# From average case complexity to improper learning complexity

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2013.

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

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [On the Computational Complexity of Ethics: Moral Tractability for Minds and Machines](https://mlsanity.com/paper/2302.04218/) (2023)
- [On the Hardness of Learning Regular Expressions](https://mlsanity.com/paper/2510.04834/) (2025)
- [Limitations of Membership Queries in Testable Learning](https://mlsanity.com/paper/2512.02279/) (2025)
- [On the Computational Benefit of Multimodal Learning](https://mlsanity.com/paper/2309.13782/) (2023)
- [Applying statistical learning theory to deep learning](https://mlsanity.com/paper/2311.15404/) (2023)
- [Improper Reinforcement Learning with Gradient-based Policy Optimization](https://mlsanity.com/paper/2102.08201/) (2021)
- [Computational-Statistical Tradeoffs from NP-hardness](https://mlsanity.com/paper/2507.13222/) (2025)

## Abstract (arXiv)

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds fall short of the best known algorithms. The biggest challenge in proving complexity results is to establish hardness of em improper learning (a.k.a. representation independent learning).The difficulty in proving lower bounds for improper learning is that the standard reductions from NP-hard problems do not seem to apply in this context. There is essentially only one known approach to proving lower bounds on improper learning. It was initiated in (Kearns and Valiant 89) and relies on cryptographic assumptions. We introduce a new technique for proving hardness of improper learning, based on reductions from problems that are hard on average. We put forward a (fairly strong) generalization of Feige's assumption (Feige 02) about the complexity of refuting random constraint satisfaction problems. Combining this assumption with our new technique yields far reaching implications. In particular, 1. Learning DNF's is hard. 2. Agnostically learning halfspaces with a constant approximation ratio is hard. 3. Learning an intersection of ω(1) halfspaces is hard.