Learning with Distributional Inverters
summary
A three-step reduction turns learning a concept over a samplable distribution D into learning over the uniform distribution by defining g(z) = f(sampler(z)), using an distributional inverter (Impagliazzo–Luby) to map samples back to coins, and running a uniform-learning algorithm on g; error combines additively (final error ≤ learning error + inverter statistical distance). Results: AC0[q] is learnable over succinct product distributions in randomized quasi-polynomial time with membership queries given the biases, and, under a strongly useful natural property, poly-size circuits are learnable over any efficiently samplable D in randomized polynomial time, but the reduction requires white-box access to the sampler code.
AI-written summary · about
chapters (8)
- 0:00Introduction to the problem
- 1:03Results and motivation
- 4:45Prior work and overview
- 10:46The reduction algorithm
- 17:00Distributional inversion
- 23:33Correctness proof
- 29:52Complexity and cryptography
- 35:38Open problems and conclusion
related talks
48mA New Paradigm for Learning with Distribution Shift
35mSublinear-Time Algorithms in Learning
45mTesting and Learning Distributions Under Local Information Constraints
01h 12mLearning probability distributions; what can, what can't be done
33mLearning and Testing Structured Distributions
39mTowards a Characterization of Differentially Private Learning
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
43mEfficient Distance Estimation And Causal Inference For Discrete Models