# Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization

arXiv: https://arxiv.org/abs/2102.04259 · HTML: https://mlsanity.com/paper/2102.04259/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 4 Feb 2021.

## Builds on (most cited first, 7 of 7)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)

## Built on by (most cited first, 4 of 4)

- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [The Relative Gaussian Mechanism and its Application to Private Gradient Descent](https://mlsanity.com/paper/2308.15250/) (2023)
- [Global convergence of gradient descent for phase retrieval](https://mlsanity.com/paper/2410.09990/) (2024)
- [Meta-learning of shared linear representations beyond well-specified linear regression](https://mlsanity.com/paper/2501.18975/) (2025)

## Abstract (arXiv)

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.