5 ms·

It seems close to simulated annealing in the travelling salesman problem. The basics of it is that you start with a random tour and adjust path segments increm

by daenz 7y ago

It seems close to simulated annealing in the travelling salesman problem. The basics of it is that you start with a random tour and adjust path segments incrementally. Most of the time, you choose a new path segment that decreases the global route cost, but randomly, you choose a new path segment that increases the global route cost. This random factor is decreased over time, so the route anneals and settles on a close-to-optimal result. It shares the same principle of choosing reasonable options most of the time, but allowing variation to keep from getting stuck in a local optimum.

opportune 7y ago
Basically you are comparing one strategy to prevent local optima in one optimization algorithm to another strategy in a different optimization algorithm. There are such strategies for basically every optimization problem. Other examples: momentum in deep learning, tabu search, random search, etc. The benefit of doing a pure binary A/B test is that the experiment is so simple that as long as you don't break the cardinal rules (you need a fixed experiment size! Most people don't even do this. Also you need to not bias your control/experiment sets) it is easy to get statistically valid results. When doing multivariate optimization using something that is measured (such as user engagement) rather than evaluated, you need a good amount of data for each configuration to evaluate it, or you run the risk of optimizing for random noise. This is true of even the multi-armed bandit problem: if you vary the exploitation strategies over time, then confounding temporal variables (for example, purchases are higher on weekdays because that's when people make business decisions at work) can invalidate the experiment if not controlled for.
- marcosdumay 7y ago
  The GP is comparing the algorithms. MAB is exactly simulated annealing with an exponential temperature.

by daenz 7y ago

opportune 7y ago

Basically you are comparing one strategy to prevent local optima in one optimization algorithm to another strategy in a different optimization algorithm. There are such strategies for basically every optimization problem. Other examples: momentum in deep learning, tabu search, random search, etc. The benefit of doing a pure binary A/B test is that the experiment is so simple that as long as you don't break the cardinal rules (you need a fixed experiment size! Most people don't even do this. Also you need to not bias your control/experiment sets) it is easy to get statistically valid results. When doing multivariate optimization using something that is measured (such as user engagement) rather than evaluated, you need a good amount of data for each configuration to evaluate it, or you run the risk of optimizing for random noise. This is true of even the multi-armed bandit problem: if you vary the exploitation strategies over time, then confounding temporal variables (for example, purchases are higher on weekdays because that's when people make business decisions at work) can invalidate the experiment if not controlled for.

marcosdumay 7y ago
The GP is comparing the algorithms. MAB is exactly simulated annealing with an exponential temperature.