More data speeds up training time in learning halfspaces over sparse vectors

The increased availability of data in recent years led several authors to ask whether it is possible to use data as a {\em computational} resource. That is, if more data is available, beyond the sampl