# Statistical optimality conditions for compressive ensembles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 76 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Random Projections through multiple optical scattering: Approximating kernels at the speed of light](https://mlsanity.com/paper/1510.06664/) (2015)
- [Precise expressions for random projections: Low-rank approximation and randomized Newton](https://mlsanity.com/paper/2006.10653/) (2020)
- [Optical machine learning with incoherent light and a single-pixel detector](https://mlsanity.com/paper/1904.10851/) (2019)
- [DUAL-LOCO: Distributing Statistical Estimation Using Random Projections](https://mlsanity.com/paper/1506.02554/) (2015)
- [Random projections: data perturbation for classification problems](https://mlsanity.com/paper/1911.10800/) (2019)
- [RaSE: Random Subspace Ensemble Classification](https://mlsanity.com/paper/2006.08855/) (2020)
- [On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/1706.10110/) (2017)
- [Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves](https://mlsanity.com/paper/1907.06969/) (2019)
- [On Principal Components Regression, Random Projections, and Column Subsampling](https://mlsanity.com/paper/1709.08104/) (2017)
- [Don't take it lightly: Phasing optical random projections with unknown operators](https://mlsanity.com/paper/1907.01703/) (2019)
- [Bounds on the Number of Measurements for Reliable Compressive Classification](https://mlsanity.com/paper/1607.02801/) (2016)
- [Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours](https://mlsanity.com/paper/1803.00310/) (2018)
- [Classification and Reconstruction of High-Dimensional Signals from Low-Dimensional Features in the Presence of Side Information](https://mlsanity.com/paper/1412.0614/) (2014)

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

- [On unsupervised projections and second order signals](https://mlsanity.com/paper/2204.05139/) (2022)

## Abstract (arXiv)

We present a framework for the theoretical analysis of ensembles of low-complexity empirical risk minimisers trained on independent random compressions of high-dimensional data. First we introduce a general distribution-dependent upper-bound on the excess risk, framed in terms of a natural notion of compressibility. This bound is independent of the dimension of the original data representation, and explains the in-built regularisation effect of the compressive approach. We then instantiate this general bound to classification and regression tasks, considering Johnson-Lindenstrauss mappings as the compression scheme. For each of these tasks, our strategy is to develop a tight upper bound on the compressibility function, and by doing so we discover distributional conditions of geometric nature under which the compressive algorithm attains minimax-optimal rates up to at most poly-logarithmic factors. In the case of compressive classification, this is achieved with a mild geometric margin condition along with a flexible moment condition that is significantly more general than the assumption of bounded domain. In the case of regression with strongly convex smooth loss functions we find that compressive regression is capable of exploiting spectral decay with near-optimal guarantees. In addition, a key ingredient for our central upper bound is a high probability uniform upper bound on the integrated deviation of dependent empirical processes, which may be of independent interest.