Despite stunning performances, state of the art machine learning approaches are often computational intensive and efficiency remains a challenge. Dimensionality reduction, if performed efficiently, provides a way to reduce the computational requirements of downstream tasks, but possibly at the expanses of the obtained accuracy. In this talk, we discuss the interplay between accuracy and efficiency when dimensionality reduction is performed by means of, possibly data dependent, random projections. The latter are related to discretization methods for integral operators, to sampling methods in randomized numerical linear algebra and to sketching methods. Our results show that there are number of different tasks and regimes where, using random projections and regularization, efficiency can be improved with no costs in accuracy. Theoretical results are used to derive scalable and fast kernel methods for datasets with millions of points.