# Accelerating ERM for data-driven algorithm design using output-sensitive techniques

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 62 references that are in the map.
- First posted on arXiv 7 Apr 2022.

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

- [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)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Learning Complexity of Simulated Annealing](https://mlsanity.com/paper/2003.02981/) (2020)
- [An Analysis of Robustness of Non-Lipschitz Networks](https://mlsanity.com/paper/2010.06154/) (2020)
- [A Sample Complexity Measure with Applications to Learning Optimal Auctions](https://mlsanity.com/paper/1704.02598/) (2017)
- [Online Optimization of Smoothed Piecewise Constant Functions](https://mlsanity.com/paper/1604.01999/) (2016)
- [On the Tractability of Public Persuasion with No Externalities](https://mlsanity.com/paper/1906.07359/) (2019)
- [Active Metric Learning for Supervised Classification](https://mlsanity.com/paper/1803.10647/) (2018)

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

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Subsidy design for better social outcomes](https://mlsanity.com/paper/2409.03129/) (2024)
- [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)

## Abstract (arXiv)

Data-driven algorithm design is a promising, learning-based approach for beyond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial algorithm families with multiple parameters. As one fixes the problem instance and varies the parameters, the "dual" loss function typically has a piecewise-decomposable structure, i.e. is well-behaved except at certain sharp transition boundaries. In this work we initiate the study of techniques to develop efficient ERM learning algorithms for data-driven algorithm design by enumerating the pieces of the sum dual loss functions for a collection of problem instances. The running time of our approach scales with the actual number of pieces that appear as opposed to worst case upper bounds on the number of pieces. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes using tools from computational geometry, and an execution graph which compactly represents all the states the algorithm could attain for all possible parameter values. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.