Optimally Compressed Nonparametric Online Learning
This work provides a survey of compression techniques for enabling nonparametric methods in online settings, which is incremental but relevant for applications like robotics and communications.
The paper addresses the curse of dimensionality in nonparametric online learning, where complexity scales with time, by surveying compression tools that control memory and achieve approximate convergence with a trade-off between memory and accuracy.
Batch training of machine learning models based on neural networks is now well established, whereas to date streaming methods are largely based on linear models. To go beyond linear in the online setting, nonparametric methods are of interest due to their universality and ability to stably incorporate new information via convexity or Bayes' Rule. Unfortunately, when used online, nonparametric methods suffer a "curse of dimensionality" which precludes their use: their complexity scales at least with the time index. We survey online compression tools which bring their memory under control and attain approximate convergence. The asymptotic bias depends on a compression parameter that trades off memory and accuracy. Further, the applications to robotics, communications, economics, and power are discussed, as well as extensions to multi-agent systems.