Timezone: »

 
Poster
Near-optimal sample compression for nearest neighbors
Lee-Ad Gottlieb · Aryeh Kontorovich · Pinhas Nisnevitch

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None

We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our bound is nearly optimal. Our result yields new insight into margin-based nearest neighbor classification in metric spaces and allows us to significantly sharpen and simplify existing bounds. Some encouraging empirical results are also presented.

Author Information

Lee-Ad Gottlieb (Ariel University)
Aryeh Kontorovich (Ben Gurion University)
Pinhas Nisnevitch (Ariel University)

More from the Same Authors