Dimension-free error bounds from random projections
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Authors
Colleges, School and Institutes
Abstract
Learning from high dimensional data is challenging in general – however, often the data is not truly high dimensional in the sense that it may have some hidden low complexity geometry. We give new, user-friendly PAC-bounds that are able to take advantage of such benign geometry to reduce dimensional-dependence of error-guarantees in settings where such dependence is known to be essential in general. This is achieved by employing random projection as an analytic tool, and exploiting its structure-preserving compression ability. We introduce an auxiliary function class that operates on reduced dimensional inputs, and a new complexity term, as the distortion of the loss under random projections. The latter is a hypothesis-dependent data-complexity, whose analytic estimates turn out to recover various regularisation schemes in parametric models, and a notion of intrinsic dimension, as quantified by the Gaussian width of the input support in the case of the nearest neighbour rule. If there is benign geometry present, then the bounds become tighter, otherwise they recover the original dimension-dependent bounds.
Details
Original language | English |
---|---|
Title of host publication | Thirty Third AAAI Conference on Artificial Intelligence (AAAI-19) |
Publication status | Published - 17 Jul 2019 |
Event | Thirty Third AAAI Conference on Artificial Intelligence (AAAI-19) - Honolulu, Hawaii, United States Duration: 27 Jan 2019 → 1 Feb 2019 |
Publication series
Name | Proceedings of the AAAI Conference on Artificial Intelligence |
---|---|
Publisher | AAAI |
Number | 1 |
Volume | 33 |
ISSN (Print) | 2159-5399 |
ISSN (Electronic) | 2374-3468 |
Conference
Conference | Thirty Third AAAI Conference on Artificial Intelligence (AAAI-19) |
---|---|
Country | United States |
City | Honolulu, Hawaii |
Period | 27/01/19 → 1/02/19 |