Answers.Body: <p>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 <em>Search-Based Software Engineering</em>. Here are the ones I know of.</p>
  
  <ul>
  <li><p>Jerry Swan and Nathan Burles. <em>Templar - A Framework for Template-Method Hyper-Heuristics</em>. 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.</p>
  
  <ul>
  <li>This paper describes 'Hyper-quicksort', a quicksort variant that uses Machine Learning (ML) to generate a pivot function:</li>
  </ul></li>
  <li><p>A. E. I. Brownlee, N. Burles, and J. Swan. <a href="http://eprints.whiterose.ac.uk/117916/1/07935484_1.pdf" rel="nofollow noreferrer"><em>Search-Based Energy Optimization of Some Ubiquitous Algorithms</em></a>. In: IEEE Transactions on Emerging Topics in Computational Intelligence 1.3 (2017), pp. 188–201. </p>
  
  <ul>
  <li>This paper uses ML to generate energy-efficient variants of some widely-used algorithms</li>
  </ul></li>
  <li><p>David R. White, Leonid Joffe, Edward Bowles, and Jerry Swan. <em><a href="http://eprints.whiterose.ac.uk/117963/1/optimizing_akka_concurrency.pdf" rel="nofollow noreferrer">Deep Parameter Tuning of Concurrent Divide and Conquer Algorithms in Akka</a></em>. ISBN: 978-3-319-55792-2.</p>
  
  <ul>
  <li>This paper uses ML to optimise the FFT, matrix multiplication and quicksort for concurrency</li>
  </ul></li>
  <li><p>Nathan Burles, Edward Bowles, Alexander E. I. Brownlee, Zoltan A. Kocsis, Jerry Swan, and Nadarajen Veerapen. <em>Object-Oriented Genetic Improvement for Improved Energy Consumption in Google Guava</em>. DOI: 10.1007/978-3-319-22183-0_20.</p>
  
  <ul>
  <li>This one optimises Google Guava for energy consumption</li>
  </ul></li>
  <li><p>Zoltan A. Kocsis, Geoff Neumann, Jerry Swan, Michael G. Epitropakis, Alexander E. I. Brownlee, Saemundur O. Haraldsson, and Edward Bowles. <em><a href="https://www.researchgate.net/publication/264155239_Repairing_and_Optimizing_Hadoop_hashCode_Implementations" rel="nofollow noreferrer">Repairing and Optimizing Hadoop hashCode Implementations</a></em>. In: Search-Based Software Engineering: 6th International Symposium, SSBSE 2014, DOI: 10.1007/978-3-319-09940-8_22.</p>
  
  <ul>
  <li>This one fixes broken hashCodes by using ML to generate new ones</li>
  </ul></li>
  </ul>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-21T17:56:33.007Z
Answers.LastActivityDate: 2019-08-18T22:24:15.890Z
Answers.LastEditDate: 2019-08-18T22:24:15.890Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph:</p>
  
  <pre><code>for o in my_graph.getDerivedObjects():
    if hasPropertyX(o):
      process(o)
      break;
  </code></pre>
  
  <p>If one of the derived objects has property <span class="math-container">$X$</span>, then the algorithm process it and then stops. The theory ensures that at least one of these derived objects has property <span class="math-container">$X$</span>. Now, I strongly suspect that there is a strong correlation between some topological aspects of the graph, and which derived objects actually have property <span class="math-container">$X$</span>. I want to <em>predict</em> some of the derived objects that have property <span class="math-container">$X$</span> using Machine Learning. So, the idea is:</p>
  
  <ol>
  <li><p>Predict a derived object <span class="math-container">$o$</span> that supposedly has property <span class="math-container">$X$</span> - or maybe predict <span class="math-container">$n$</span> of them for some number <span class="math-container">$n$</span>.</p></li>
  <li><p>If any of them is useful, I use them. If not, I run the exponential algorithm.</p></li>
  </ol>
  
  <p>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.</p>
  
  <p>Is this type of optimizations common? Could you please provide some examples? The literature on the subject would also be greatly appreciated.</p>
  
Tags: <algorithm><applications><time-complexity>
Title: Can machine learning be used to improve the average case complexity of an algorithm?
UserDisplayName: Guillermo Mosse
ThreadText: # Can machine learning be used to improve the average case complexity of an algorithm?
  
  (Asked by: username_0 on 2019-03-17)
  
  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.
  
  **Tags:** algorithm, applications, time-complexity
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-21. Score: 3
  
  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*](http://eprints.whiterose.ac.uk/117916/1/07935484_1.pdf). 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](http://eprints.whiterose.ac.uk/117963/1/optimizing_akka_concurrency.pdf)*. 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](https://www.researchgate.net/publication/264155239_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.
  
  
  ---
  
  