Competing against the Best Nearest Neighbor Filter in Regression

Arnak S. Dalalyan, Joseph Salmon

Abstract

Designing statistical procedures that are provably almost as accurate as the best one in a given family is one of central topics in statistics and learning theory. Oracle inequalities offer then a convenient theoretical framework for evaluating different strategies, which can be roughly classified into two classes: selection and aggregation strategies. The ultimate goal is to design strategies satisfying oracle inequalities with leading constant one and rate-optimal residual term. In many recent papers, this problem is addressed in the case where the aim is to beat the best procedure from a given family of linear smoothers. However, the theory developed so far either does not cover the important case of nearest-neighbor smoothers or provides a suboptimal oracle inequality with a leading constant considerably larger than one. In this paper, we prove a new oracle inequality with leading constant one that is valid under a general assumption on linear smoothers allowing, for instance, to compete against the best nearest-neighbor filters.
BibTeX
@inproceedings{dalalyan2011competing,
  author = {Arnak S. Dalalyan and Joseph Salmon},
  title = {{Competing against the Best Nearest Neighbor Filter in Regression}},
  booktitle = {ALT},
  year = {2011},
  doi = {10.1007/978-3-642-24412-4\_13},
}

Loading related content...

Figure