4 ms·

I'm not sure why the author picks Myth #5 as the big pro-frequentist point. The "online learning" problem he's describing is a simple multi-armed bandit problem

by tansey 13y ago

I'm not sure why the author picks Myth #5 as the big pro-frequentist point. The "online learning" problem he's describing is a simple multi-armed bandit problem. The magical frequentist algorithm that he's touting is UCB-1. It's a great algorithm, it has finite-time optimality guarantees like he mentions. However, it still has a tuning parameter that can matter quite a bit in practice. Also, the Bayesian approach to MABs is Thompson sampling, which is also finite-time optimal. I guess I don't get the big deal on this point. From a machine learning perspective, frequentist methods are great because they scale. All of these fancy nonparametric Bayes methods coming out these days take weeks to run and include so many approximations that you've got no idea whether what you're actually inferring is truly similar to the original model. The biggest problem with frequentist methods is that they are conceptually odd in their approach. Bayesians take the view that you should fix the data and integrate over the possible parameters. Frequentists take the view that you should fix the parameters and integrate over the data. That is kind of weird to me. So you either start out conceptually pure as a Bayesian and compromise to the point of meaninglessness or you abandon your morals at the start as a frequentist and things go smoothly from there. Edit: As noted below, it's actually Exp3 rather than UCB-1. I glossed over the part about potentially adversarial bandits.

noelwelsh 13y ago
Actually it's not UCB-1. UCB-1 solves the stochastic bandit problem, where you assume the arms have fixed but unknown expected reward. He's talking about the adversarial setting, where you make no assumptions about the distribution of the rewards of the arms. They can even be set by an adversary that is trying to make you perform badly. Remarkably you can derive results here, though the "catch" is you are measuring performance against choosing a fixed arm for every play. (It's actually a bit more complex than that, but that's a reasonable simplification for direct comparison to the stochastic bandit.) The standard algorithm in the adversarial setting is Exp3: http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf Otherwise I agree for the most part with what you've said. Edit: In response to the parent edit, I should note that I know of no Bayesian algorithm for the adversarial setting. Thompson sampling is assuming a stochastic problem. I think a Bayesian algorithm would be possible, but the details elude me.
- tansey 13y ago
  Same here. I was thinking after my edit that I don't know of such an algorithm either, but I don't think in principle that there is anything stopping someone from coming up with one. So... who wants a NIPS paper? Noel and I are happy to just be 2nd authors, since you know... it was our idea and everything. ;)
  - noelwelsh 13y ago
    Hell yeah. First author gets to do the poster session. I'll do the skiing. ;-)
idunning 13y ago
I don't believe that is correct, re: UCB1 There are probably a few ways to prove the result now, but one (nicely general) way to prove that online learning result would be the method of multiplicative weights: https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
thisisdave 13y ago
>Frequentists take the view that you should fix the parameters and integrate over the data. That is kind of weird to me. Integrating over the data makes a lot of sense during methods development. If you're the inventor of some algorithm and you want to convince people that they should apply it to their data set, then you'd want to show that it works well on a range of possible data sets. It also makes some sense during policy development. Over your lifetime, you're going to see a lot of data sets, and having some policy about which statements about those data sets to believe can be useful. This policy doesn't have to be P<0.05. It could be six-sigma (like in physics) or something based on the false discovery rate (like in genomics). I don't think frequentism is always the right approach, but I do see a place for it.

by tansey 13y ago

noelwelsh 13y ago

Actually it's not UCB-1. UCB-1 solves the stochastic bandit problem, where you assume the arms have fixed but unknown expected reward. He's talking about the adversarial setting, where you make no assumptions about the distribution of the rewards of the arms. They can even be set by an adversary that is trying to make you perform badly. Remarkably you can derive results here, though the "catch" is you are measuring performance against choosing a fixed arm for every play. (It's actually a bit more complex than that, but that's a reasonable simplification for direct comparison to the stochastic bandit.) The standard algorithm in the adversarial setting is Exp3: http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf Otherwise I agree for the most part with what you've said. Edit: In response to the parent edit, I should note that I know of no Bayesian algorithm for the adversarial setting. Thompson sampling is assuming a stochastic problem. I think a Bayesian algorithm would be possible, but the details elude me.

tansey 13y ago
Same here. I was thinking after my edit that I don't know of such an algorithm either, but I don't think in principle that there is anything stopping someone from coming up with one. So... who wants a NIPS paper? Noel and I are happy to just be 2nd authors, since you know... it was our idea and everything. ;)
- noelwelsh 13y ago
  Hell yeah. First author gets to do the poster session. I'll do the skiing. ;-)

idunning 13y ago

I don't believe that is correct, re: UCB1 There are probably a few ways to prove the result now, but one (nicely general) way to prove that online learning result would be the method of multiplicative weights: https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

thisisdave 13y ago

>Frequentists take the view that you should fix the parameters and integrate over the data. That is kind of weird to me. Integrating over the data makes a lot of sense during methods development. If you're the inventor of some algorithm and you want to convince people that they should apply it to their data set, then you'd want to show that it works well on a range of possible data sets. It also makes some sense during policy development. Over your lifetime, you're going to see a lot of data sets, and having some policy about which statements about those data sets to believe can be useful. This policy doesn't have to be P<0.05. It could be six-sigma (like in physics) or something based on the false discovery rate (like in genomics). I don't think frequentism is always the right approach, but I do see a place for it.