Can machine learning be used to improve the average case complexity of an algorithm?
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.