Abstract
Averaging ensembles of randomly oriented low-dimensional projections of a singular co-variance represent a novel and attractive means to obtain a well-conditioned inverse, which only needs access to random projections of the data. However, theoretical analyses so far have only been done at convergence, implying good properties for ‘large-enough’ ensembles. But how large is ‘large enough’? Here we bound the expected difference in spectral norm between the finite ensemble precision matrix and the infinite ensemble, and based on this we give an estimate of the required ensemble size to guarantee the approximation
error of the finite ensemble is below a given tolerance. Under mild assumptions, we find that for any given tolerance, the ensemble only needs to grow linearly in the original data dimension. A technical ingredient of our analysis is to upper bound the spectral norm of a matrix-variate T, which we then employ in conjunction with specific results from random matrix theory regarding the estimation of the covariance of random matrices.
error of the finite ensemble is below a given tolerance. Under mild assumptions, we find that for any given tolerance, the ensemble only needs to grow linearly in the original data dimension. A technical ingredient of our analysis is to upper bound the spectral norm of a matrix-variate T, which we then employ in conjunction with specific results from random matrix theory regarding the estimation of the covariance of random matrices.
Original language | English |
---|---|
Title of host publication | Proceedings of 28th International Conference on Algorithmic Learning Theory (ALT 2017) |
Publisher | JMLR |
Number of pages | 15 |
Publication status | Accepted/In press - 24 Jul 2017 |
Event | 28th International Conference on Algorithmic Learning Theory (ALT 2017) - Kyoto, Japan Duration: 15 Oct 2017 → 17 Oct 2017 |
Publication series
Name | Proceedings of Machine Learning Research |
---|---|
Publisher | PMLR |
Volume | 76 |
ISSN (Electronic) | 1938-7228 |
Conference
Conference | 28th International Conference on Algorithmic Learning Theory (ALT 2017) |
---|---|
Country/Territory | Japan |
City | Kyoto |
Period | 15/10/17 → 17/10/17 |
Keywords
- Ensemble learning
- Compressive learning
- Random matrix theory
- Matrix- variate T