# (Machine) Learning to Improve the Empirical Performance of Discrete Algorithms

arXiv: https://arxiv.org/abs/2109.14271 · HTML: https://mlsanity.com/paper/2109.14271/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 56 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 13 of 13)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [OBOE: Collaborative Filtering for AutoML Model Selection](https://mlsanity.com/paper/1808.03233/) (2018)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [The Voice of Optimization](https://mlsanity.com/paper/1812.09991/) (2018)
- [Pitfalls and Best Practices in Algorithm Configuration](https://mlsanity.com/paper/1705.06058/) (2017)
- [ICON Challenge on Algorithm Selection](https://mlsanity.com/paper/1511.04326/) (2015)
- [A Friendly Smoothed Analysis of the Simplex Method](https://mlsanity.com/paper/1711.05667/) (2017)

## Abstract (arXiv)

This paper discusses a data-driven, empirically-based framework to make algorithmic decisions or recommendations without expert knowledge. We improve the performance of two algorithmic case studies: the selection of a pivot rule for the Simplex method and the selection of an all-pair shortest paths algorithm. We train machine learning methods to select the optimal algorithm for given data without human expert opinion. We use two types of techniques, neural networks and boosted decision trees. We concluded, based on our experiments, that: 1) Our selection framework recommends various pivot rules that improve overall total performance over just using a fixed default pivot rule. Over many years experts identified steepest-edge pivot rule as a favorite pivot rule. Our data analysis corroborates that the number of iterations by steepest-edge is no more than 4 percent more than the optimal selection which corroborates human expert knowledge, but this time the knowledge was obtained using machine learning. Here our recommendation system is best when using gradient boosted trees. 2) For the all-pairs shortest path problem, the models trained made a large improvement and our selection is on average .07 percent away from the optimal choice. The conclusions do not seem to be affected by the machine learning method we used. We tried to make a parallel analysis of both algorithmic problems, but it is clear that there are intrinsic differences. For example, in the all-pairs shortest path problem the graph density is a reasonable predictor, but there is no analogous single parameter for decisions in the Simplex method.