If δ(k,j)∈Δ2avg, for what functions g does δ(k,g(k))→0?
Does this require j to grow faster than any quasipolynomial function of k? Because that’s pretty fast. I guess it’s clear that j is going to have to increase faster than any polynomial in k?
There are no functions with this property. You have to do the log-log uniform average over js (up to a superquasipolynomial function) in order to guarantee convergence to 0 (however if you have a perfect predictor then you can amplify so that the error behaves like you described). I think it’s possible to change the formalism in a way which replaces quasipolynomials by polynomials and superquasipolynomial functions by superpolynomial functions but this requires introducing assumptions about the computational model so I avoided it for now.
Note though that superquasipolynomial is still “far from exponential” in some sense because there is a natural infinite tower of complexities between polynomial and exponential where 0-th level is polynomial functions and the n+1-st level consists of functions of the form 2f(logn) where f is a function of the n-th level (so quasipolynomials are level 1).
Btw, if you’re trying to catch up on optimal predictors then I have a nearly finished draft of a paper with an orderly presentation and consistent notation that I can send you.
If δ(k,j)∈Δ2avg, for what functions g does δ(k,g(k))→0?
Does this require j to grow faster than any quasipolynomial function of k? Because that’s pretty fast. I guess it’s clear that j is going to have to increase faster than any polynomial in k?
There are no functions with this property. You have to do the log-log uniform average over js (up to a superquasipolynomial function) in order to guarantee convergence to 0 (however if you have a perfect predictor then you can amplify so that the error behaves like you described). I think it’s possible to change the formalism in a way which replaces quasipolynomials by polynomials and superquasipolynomial functions by superpolynomial functions but this requires introducing assumptions about the computational model so I avoided it for now.
Note though that superquasipolynomial is still “far from exponential” in some sense because there is a natural infinite tower of complexities between polynomial and exponential where 0-th level is polynomial functions and the n+1-st level consists of functions of the form 2f(logn) where f is a function of the n-th level (so quasipolynomials are level 1).
Btw, if you’re trying to catch up on optimal predictors then I have a nearly finished draft of a paper with an orderly presentation and consistent notation that I can send you.