Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
arXiv:2102.04259
Abstract
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.
References in corpus (6)
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- Approximating the moments of marginals of high-dimensional distributions
- Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
- Comparison-Based Learning with Rank Nets
- A law of robustness for two-layers neural networks
- Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction