Before revision:  OurO\big({} \big)  main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data ~ -- ~ all of them crucially take the structure of the underlying halfspace into account .
After revision:  OurO\big({\frac 1 \epsilon s^2 \log^5 d} \big) main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data ~ -- ~ all of them crucially take the structure of the underlying halfspace into account .