TY - GEN
T1 - Dimension-free error bounds from random projections
AU - Kaban, Ata
PY - 2019/7/17
Y1 - 2019/7/17
N2 - 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.
AB - 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.
U2 - 10.1609/aaai.v33i01.33014049
DO - 10.1609/aaai.v33i01.33014049
M3 - Conference contribution
SN - 978-1-57735-809-1
T3 - Proceedings of the AAAI Conference on Artificial Intelligence
SP - 4049
EP - 4056
BT - Thirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
PB - AAAI Press
T2 - Thirty Third AAAI Conference on Artificial Intelligence (AAAI-19)
Y2 - 27 January 2019 through 1 February 2019
ER -