# On the Tradeoff between Stability and Fit

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2013.

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

- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)

## Abstract (arXiv)

In computing, as in many aspects of life, changes incur cost. Many optimization problems are formulated as a one-time instance starting from scratch. However, a common case that arises is when we already have a set of prior assignments, and must decide how to respond to a new set of constraints, given that each change from the current assignment comes at a price. That is, we would like to maximize the fitness or efficiency of our system, but we need to balance it with the changeout cost from the previous state. We provide a precise formulation for this tradeoff and analyze the resulting em stable extensions of some fundamental problems in measurement and analytics. Our main technical contribution is a stable extension of PPS (probability proportional to size) weighted random sampling, with applications to monitoring and anomaly detection problems. We also provide a general framework that applies to top-k, minimum spanning tree, and assignment. In both cases, we are able to provide exact solutions, and discuss efficient incremental algorithms that can find new solutions as the input changes.