Dimension-free error bounds from random projections

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publicationThirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
Publication statusAccepted/In press - 31 Oct 2018
EventThirty Third AAAI Conference on Artificial Intelligence (AAAI-19) - Honolulu, Hawaii, United States
Duration: 27 Jan 20191 Feb 2019

Conference

ConferenceThirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
CountryUnited States
CityHonolulu, Hawaii
Period27/01/191/02/19