# Data-driven Algorithm Design

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2020.

## Built on by (most cited first, 5 of 5)

- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026)
- [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026)
- [Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems](https://mlsanity.com/paper/2411.08332/) (2024)

## Abstract (arXiv)

Data driven algorithm design is an important aspect of modern data science and algorithm design. Rather than using off the shelf algorithms that only have worst case performance guarantees, practitioners often optimize over large families of parametrized algorithms and tune the parameters of these algorithms using a training set of problem instances from their domain to determine a configuration with high expected performance over future instances. However, most of this work comes with no performance guarantees. The challenge is that for many combinatorial problems of significant importance including partitioning, subset selection, and alignment problems, a small tweak to the parameters can cause a cascade of changes in the algorithm's behavior, so the algorithm's performance is a discontinuous function of its parameters. In this chapter, we survey recent work that helps put data-driven combinatorial algorithm design on firm foundations. We provide strong computational and statistical performance guarantees, both for the batch and online scenarios where a collection of typical problem instances from the given application are presented either all at once or in an online fashion, respectively.