Pattern recognition as a deterministic problem: An approach based on discrepancy

When the position of each input vector in the training set is not fixed beforehand, a deterministic approach can be adopted to face with the general problem of learning. In particular, the consistency of the Empirical Risk Minimization (ERM) principle can be established, when the points in the input space are generated through a purely deterministic algorithm (deterministic learning). When the output generation is not subject to noise, classical number-theoretic results, involving discrepancy and variation, allow to establish a sufficient condition for the consistency of the ERM principle. In addition, the adoption of low-discrepancy sequences permits to achieve a learning rate of O(1=L), being L the size of the training set.