Statistical query (SQ) learning model of Kearns (1993) is a natural\nrestriction of the PAC learning model in which a learning algorithm is allowed\nto obtain estimates of statistical properties of the examples but cannot see\nthe examples themselves. We describe a new and simple characterization of the\nquery complexity of learning in the SQ learning model. Unlike the previously\nknown bounds on SQ learning our characterization preserves the accuracy and the\nefficiency of learning. The preservation of accuracy implies that that our\ncharacterization gives the first characterization of SQ learning in the\nagnostic learning framework. The preservation of efficiency is achieved using a\nnew boosting technique and allows us to derive a new approach to the design of\nevolutionary algorithms in Valiant's (2006) model of evolvability. We use this\napproach to demonstrate the existence of a large class of monotone evolutionary\nlearning algorithms based on square loss performance estimation. These results\ndiffer significantly from the few known evolutionary algorithms and give\nevidence that evolvability in Valiant's model is a more versatile phenomenon\nthan there had been previous reason to suspect.\n