Dimension-free error bounds from random projections

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)
182 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationThirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
PublisherAAAI Press
Number of pages8
ISBN (Print)978-1-57735-809-1
Publication statusPublished - 17 Jul 2019
EventThirty Third AAAI Conference on Artificial Intelligence (AAAI-19) - Honolulu, Hawaii, United States
Duration: 27 Jan 20191 Feb 2019

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceThirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
Country/TerritoryUnited States
CityHonolulu, Hawaii


Dive into the research topics of 'Dimension-free error bounds from random projections'. Together they form a unique fingerprint.

Cite this