  Dimension is an inherent bottleneck to some modern learning tasks, where
optimization methods suffer from the size of the data. In this paper, we study
non-isotropic distributions of data and develop tools that aim at reducing
these dimensional costs by a dependency on an effective dimension rather than
the ambient one. Based on non-asymptotic estimates of the metric entropy of
ellipsoids -- that prove to generalize to infinite dimensions -- and on a
chaining argument, our uniform concentration bounds involve an effective
dimension instead of the global dimension, improving over existing results. We
show the importance of taking advantage of non-isotropic properties in learning
problems with the following applications: i) we improve state-of-the-art
results in statistical preconditioning for communication-efficient distributed
optimization, ii) we introduce a non-isotropic randomized smoothing for
non-smooth optimization. Both applications cover a class of functions that
encompasses empirical risk minization (ERM) for linear models.
