Specification and simulation of statistical query algorithms for efficiency and noise tolerance (Q1271551)

The authors define the relative error statistical query model. The advantage of the statistical query models and of specifying learning algorithms in this model is that SQ algorithms can be simulated in the probably approximately correct (PAC) model, both in the absence and in the presence of noise. An open problem was an efficient time and sample complexity of such simulations. The authors show how ``efficient'' relative error statistical query algorithms can be simulated in the (PAC) model and that such efficient relative error statistical query algorithms are guaranteed to exist (so long as an SQ algorithm exists). The simulations given are in the absence of noise and in the presence of malicious errors roughly optimal. In the presence of classification noise, the simulations are no worse than similar simulations for the additive error statistical query model and under additional conditions the simulations are also roughly optimal. Finally the authors give general upper bounds on the complexity of learning algorithms achieved through the use of relative error SQ algorithms and the simulations given in the paper.