Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
This work is significant for researchers in optimization and machine learning who deal with high-dimensional data, as it offers methods to reduce computational costs by leveraging data's non-isotropic properties.
This paper addresses the dimensional bottleneck in modern learning tasks by developing tools for non-isotropic data distributions. The authors derive uniform concentration bounds that depend on an effective dimension rather than the ambient dimension, improving existing results.
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.