Earlier quoted context omitted.
Do you know of any other kinds of universal function approximators that also have a good regret bound like this, or is yours the first one? global convergence to any arbitrarily weird function at rate O(sqrt(T)) seems amazing, almost too good to be true, and I’m wondering what the catch is. Maybe it’s just a moderately nice property but not extraordinary? Maybe there are some horrible constants hiding in there?
1) It's definitely not the first. Other methods have universal guarantees of some form or other with well quantified rates of convergence, e.g. k-NN would be the best known example. 2) There are some restrictions on the class of density functions it can model, so arbitrarily weird is a bit strong, but the model class is very general. 3) The weights needed to model any function in this class although finite, can be ar…
much to chew on here, it really does seem like a very interesting class of models. from the papers it sounds like in practice clipping weights to a small set works okay, so the constant factors shouldn't be too bad.
i may have to sit down and try to implement these...