CS369N: Beyond Worst-Case Analysis Lecture #5: Self-Improving Algorithms ∗
Tim Roughgarden · 2010
Last lecture concluded with a discussion of semi-random graph models, an interpolation between worst-case analysis and average-case analysis designed to identify robust algorithms in the face of strong impossibility results for worst-case guarantees. This lecture and the next two give three more analysis frameworks that blend aspects of worst- and average-case analysis. Today’s model, of self-improving algorithms, is the closest to traditional averagecase analysis. The model and results are by Ailon, Chazelle, Comandar, and Liu [1]. The Setup. For a given computational problem, we posit a distribution over instances. The difference between today’s model and traditional average-case analysis is that the distribution is unknown. The goal is to design an algorithm that, given an online sequence of instances — each an independent and identically distributed (i.i.d.) sample — quickly converges to an algorithm that is optimal for the underlying distribution. Thus the algorithm is “automatically self-tuning. ” The challenge is to accomplish this goal with fewer “training samples ” and smaller space than a brute-force “learn the data model ” approach. Main Example: Sorting. The obvious first problem to apply the self-improving paradigm to is sorting in the comparison model, and that’s what we do here. Each instance is an array of n elements, with the ith element drawn from a real-valued distribution Di. A key assumption is that the Di’s are independent distributions; Section 5.3 discusses this assumption. The distributions need not be identical. Identical distributions are uninteresting in our context, since in this case the relative order of the elements is a uniformly random permutation. Every correct sorting algorithm requires Ω(n log n) expected comparisons in this case, and a matching upper is bound is achieved by MergeSort (say).