Can machine learning be used to improve the average case complexity of an algorithm?

Question

I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph:

for o in my_graph.getDerivedObjects():
  if hasPropertyX(o):
    process(o)
    break;

If one of the derived objects has property $X$, then the algorithm process it and then stops. The theory ensures that at least one of these derived objects has property $X$. Now, I strongly suspect that there is a strong correlation between some topological aspects of the graph, and which derived objects actually have property $X$. I want to predict some of the derived objects that have property $X$ using Machine Learning. So, the idea is:

1. Predict a derived object $o$ that supposedly has property $X$ - or maybe predict $n$ of them for some number $n$.

2. If any of them is useful, I use them. If not, I run the exponential algorithm.

Of course, this isn't an optimization in the worst-case complexity of the algorithm. Also, I suppose I should also develop some statistical tests in order to show that the prediction algorithm actually works.

Is this type of optimizations common? Could you please provide some examples? The literature on the subject would also be greatly appreciated.

Answer 1

To the best of my knowledge, there haven't yet been many academic publications in this area, which could be broadly said to fall within Search-Based Software Engineering. Here are the ones I know of.

• Jerry Swan and Nathan Burles. Templar - A Framework for Template-Method Hyper-Heuristics. In: Genetic Programming - 18th European Conference, EuroGP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. 2015, pp. 205–216. DOI: 10.1007/978-3-319-16501-1_17.

  • This paper describes 'Hyper-quicksort', a quicksort variant that uses Machine Learning (ML) to generate a pivot function:

• A. E. I. Brownlee, N. Burles, and J. Swan. Search-Based Energy Optimization of Some Ubiquitous Algorithms. In: IEEE Transactions on Emerging Topics in Computational Intelligence 1.3 (2017), pp. 188–201.

  • This paper uses ML to generate energy-efficient variants of some widely-used algorithms

• David R. White, Leonid Joffe, Edward Bowles, and Jerry Swan. Deep Parameter Tuning of Concurrent Divide and Conquer Algorithms in Akka. ISBN: 978-3-319-55792-2.

  • This paper uses ML to optimise the FFT, matrix multiplication and quicksort for concurrency

• Nathan Burles, Edward Bowles, Alexander E. I. Brownlee, Zoltan A. Kocsis, Jerry Swan, and Nadarajen Veerapen. Object-Oriented Genetic Improvement for Improved Energy Consumption in Google Guava. DOI: 10.1007/978-3-319-22183-0_20.

  • This one optimises Google Guava for energy consumption

• Zoltan A. Kocsis, Geoff Neumann, Jerry Swan, Michael G. Epitropakis, Alexander E. I. Brownlee, Saemundur O. Haraldsson, and Edward Bowles. Repairing and Optimizing Hadoop hashCode Implementations. In: Search-Based Software Engineering: 6th International Symposium, SSBSE 2014, DOI: 10.1007/978-3-319-09940-8_22.

  • This one fixes broken hashCodes by using ML to generate new ones

There was also one (from Microsoft Research, I think) entitled something like "The case for self-adjusting data structures". I'll add an edit if I can find it.