Eliezer: I recognize that the two algorithms have the exact same trajectory for the weights, that the only thing that’s different between them is the final output, not the weights. However, maybe I’m being clueless here, but I still don’t see that as justifying considering the two different proof results really comparable.
The real worst case analysis for the second algorithm would be more like “the random source just happened to (extremely unlikely, but...) always come up with the wrong answer.”
Obviously this sort of worst case analysis isn’t really fair to randomized algorithms, obviously you’d have to do something like “what’s the worst case probability of getting it wrong, blah blah blah” or some such. But then, clearly (to me, at least) it’s kinda cheating to then turn around and say “okay then, now let’s compare that to the actual worst case analysis of the deterministic algorithm and conclude the random algorithm is superior.”
On the other hand, I guess you could say that what’s being done is “let’s compare the expected value of the number of mistakes given the assumption of the most malicious possible data. In the deterministic version, that happens to be the actual actual worst case, and in the probabilistic version, well, obviously there’s other possibilities so it’s only the expected value for the worst case given the inputs.”
So I guess after all the are comparable after all.
But that only works given that one is creative about what we allow to be considered the “worst case”… that is, if we consider the worst case for the input data, but not the worst case from the random source of bits. Which… I guess was your point all along, that it’s due to the peculiar assumptions implicit in the notion of “worst case analysis”
chuckles well, I guess this is a case in point with regards to the whole “disagreement debate”… seems when I’m in disagreement with you, I end up many times, in the process of arguing my position finding that I was the one in error.
Eliezer: I recognize that the two algorithms have the exact same trajectory for the weights, that the only thing that’s different between them is the final output, not the weights. However, maybe I’m being clueless here, but I still don’t see that as justifying considering the two different proof results really comparable.
The real worst case analysis for the second algorithm would be more like “the random source just happened to (extremely unlikely, but...) always come up with the wrong answer.”
Obviously this sort of worst case analysis isn’t really fair to randomized algorithms, obviously you’d have to do something like “what’s the worst case probability of getting it wrong, blah blah blah” or some such. But then, clearly (to me, at least) it’s kinda cheating to then turn around and say “okay then, now let’s compare that to the actual worst case analysis of the deterministic algorithm and conclude the random algorithm is superior.”
On the other hand, I guess you could say that what’s being done is “let’s compare the expected value of the number of mistakes given the assumption of the most malicious possible data. In the deterministic version, that happens to be the actual actual worst case, and in the probabilistic version, well, obviously there’s other possibilities so it’s only the expected value for the worst case given the inputs.”
So I guess after all the are comparable after all.
But that only works given that one is creative about what we allow to be considered the “worst case”… that is, if we consider the worst case for the input data, but not the worst case from the random source of bits. Which… I guess was your point all along, that it’s due to the peculiar assumptions implicit in the notion of “worst case analysis”
chuckles well, I guess this is a case in point with regards to the whole “disagreement debate”… seems when I’m in disagreement with you, I end up many times, in the process of arguing my position finding that I was the one in error.