If an order of magnitude speedup is "astonishing" then the field must have become overconfident and complacent. Great to see someone rocking the boat. But does anyone care to explain any more (in English, for us plebes) more about how this is astonishing? I'm not challenging the assessment; I'm just curious about what it means.
And some interesting words from one of the other papers: what are "classifier regret" and "ranking regret"? Is that a metric of how often you go down the wrong path or something?
Are you saying an improvement from O(n^2) to O(n) is not impressive? BTW, if this is the improvement you are referring to, its not a "order of magnitude".
