# Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization

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

## Key facts

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

## Built on by (most cited first, 30 of 37)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Efficiently Learning the Graph for Semi-supervised Learning](https://mlsanity.com/paper/2306.07098/) (2023)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Aligned Textual Scoring Rules](https://mlsanity.com/paper/2507.06221/) (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)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)

## Abstract (arXiv)

Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a crucial problem in modern data science. Practitioners often optimize over a parameterized algorithm family, tuning parameters based on problems from their domain. These procedures have historically come with no guarantees, though a recent line of work studies algorithm selection from a theoretical perspective. We advance the foundations of this field in several directions: we analyze online algorithm selection, where problems arrive one-by-one and the goal is to minimize regret, and private algorithm selection, where the goal is to find good parameters over a set of problems without revealing sensitive information contained therein. We study important algorithm families, including SDP-rounding schemes for problems formulated as integer quadratic programs, and greedy techniques for canonical subset selection problems. In these cases, the algorithm's performance is a volatile and piecewise Lipschitz function of its parameters, since tweaking the parameters can completely change the algorithm's behavior. We give a sufficient and general condition, dispersion, defining a family of piecewise Lipschitz functions that can be optimized online and privately, which includes the functions measuring the performance of the algorithms we study. Intuitively, a set of piecewise Lipschitz functions is dispersed if no small region contains many of the functions' discontinuities. We present general techniques for online and private optimization of the sum of dispersed piecewise Lipschitz functions. We improve over the best-known regret bounds for a variety of problems, prove regret bounds for problems not previously studied, and give matching lower bounds. We also give matching upper and lower bounds on the utility loss due to privacy. Moreover, we uncover dispersion in auction design and pricing problems.