Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization setting. As an application, we use known natural lower bounds for $AC^0[p]$ circuits (due to Razborov and Smolensky) to get the first quasi-polynomial time algorithm for learning $AC^0[p]$ functions, in the PAC model over the uniform distribution, with membership queries.