Screening Data Points in Empirical Risk Minimization via Ellipsoidal Regions and Safe Loss Functions


Grégoire Mialon, Julien Mairal, Alexandre d’Aspremont ;
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3610-3620, 2020.


We design simple screening tests to automatically discard data samples in empirical risk minimization withoutlosing optimization guarantees. We derive loss functions that produce dual objectives with a sparse solution. We also show how to regularize convex losses to ensure such a dual sparsity-inducing property, andpropose a general method to design screening tests for classification or regression based on ellipsoidal approximations of the optimal set. In addition to producing computational gains, our approach also allows us to compress a dataset into a subset of representative points.

Related Material