☂️ Improvements to statistical exploration

[Elarnon]

This is a tracking issue for various possible improvements to Telamon's statistical exploration procedures. Ideas include:

• Some approaches (e.g. [1]) propose to learn a performance model instead of specifying one manually. One of Telamon's strength here is also a weakness, because the need to be able to predict performance for partially-specified candidates makes it harder to learn a meaningful cost function -- and we need the performance model to keep predicting an actual lower bound on the performance. However, we also use the performance model to guide the exploration in the monte-carlo exploration phase, and we could use a ranking-based model (as in [1]) to predict, for instance, the most interesting candidate to explore during a monte-carlo descent directly from features extracted from the performance model instead of using only the bound.
• Experiment with alternatives to the monte-carlo search. This includes experimenting with different hyper-parameters, different strategies for the armed bandit problem, and completely different approaches to the exploration which could be based on genetic algorithms or simulated annealing. Need to think more about how those would work wrt partial candidates :)
• Enable search across different choices. This would probably require having an efficient way to compare candidates (since the search tree would become a search DAG and we want to merge identical candidates). One possibility is to perform the search across all possible decisions instead of limiting ourselves to a single choice, but that occurs a high computational cost. We could also try to dynamically predict good choices to make, or perform meta-analysis across different kernels to improve the existing static choice order.

1: TVM: An Automated End-to-End Optimizing Compiler for Deep Learning