On Error and Compression Rates for Prototype Rules
We study the close interplay between error and compression in the
non-parametric multiclass classification setting in terms of prototype learning
rules. We focus in particular on a close variant of a recently proposed
compression-based learning rule termed OptiNet. Beyond its computational
merits, this rule has been recently shown to be universally consistent in any
metric instance space that admits a universally consistent rule -- the first
learning algorithm known to enjoy this property. However, its error and
compression rates have been left open. Here we derive such rates in the case
where instances reside in Euclidean space under commonly posed smoothness and
tail conditions on the data distribution. We first show that OptiNet achieves
non-trivial compression rates while enjoying near minimax-optimal error rates.
We then proceed to study a novel general compression scheme for further
compressing prototype rules that locally adapts to the noise level without
sacrificing accuracy. Applying it to OptiNet, we show that under a geometric
margin condition, further gain in the compression rate is achieved.
Experimental results comparing the performance of the various methods are
presented.