## Abstract

It is well known that in general, the nearest neighbour rule (NN) has sample complexity that is exponential in the input space dimension d when only smoothness is assumed on the label posterior function. Here we consider NN on randomly projected data, and we show that, if the input domain has a small ”metric size”, then the sample complexity becomes exponential in the metric entropy integral of the set of normalised chords of the input domain. This metric entropy integral measures the complexity of the input domain, and can be much smaller than d – for instance in cases when the data lies in a linear or a smooth

nonlinear subspace of the ambient space, or when it has a sparse representation. We then show that the guarantees we obtain for the compressive NN also hold for the dataspace NN in bounded domains; thus the random projection takes the role of an analytic tool to identify benign structures under which NN learning is possible from a small sample size. Numerical simulations on data designed to have intrinsically low complexity confirm our theoretical findings, and display a striking agreement in the empirical performances of compressive NN and dataspace NN. This suggests that high dimensional data sets that have a low

complexity underlying structure are well suited for computationally cheap compressive NN learning.

nonlinear subspace of the ambient space, or when it has a sparse representation. We then show that the guarantees we obtain for the compressive NN also hold for the dataspace NN in bounded domains; thus the random projection takes the role of an analytic tool to identify benign structures under which NN learning is possible from a small sample size. Numerical simulations on data designed to have intrinsically low complexity confirm our theoretical findings, and display a striking agreement in the empirical performances of compressive NN and dataspace NN. This suggests that high dimensional data sets that have a low

complexity underlying structure are well suited for computationally cheap compressive NN learning.

Original language | English |
---|---|

Title of host publication | ACML 2015 Proceedings |

Publisher | JMLR |

Pages | 65-80 |

Number of pages | 16 |

Volume | 45 |

Publication status | Published - 25 Feb 2016 |

Event | 7th Asian Conference on Machine Learning - Hong Kong, China Duration: 20 Nov 2015 → 22 Nov 2015 |

### Publication series

Name | Proceedings of Machine Learning Research |
---|---|

Volume | 45 |

ISSN (Print) | 1938-7228 |

### Conference

Conference | 7th Asian Conference on Machine Learning |
---|---|

Country/Territory | China |

City | Hong Kong |

Period | 20/11/15 → 22/11/15 |