The proposed method uses homonymous and heteronymous examplepairs to train a linear preprocessor on a kernel-induced Hilbert space. The algorithm seeks to optimize the expected performance of elementary classifiers to be generated from single future training examples. The method is justified by PAC-style generalization guarantees and the resulting algorithm has been tested on problems of geometrically invariant pattern recognition and face verification.