  We develop a framework for the rigorous analysis of focused stochastic local
search algorithms. These are algorithms that search a state space by repeatedly
selecting some constraint that is violated in the current state and moving to a
random nearby state that addresses the violation, while hopefully not
introducing many new ones. An important class of focused local search
algorithms with provable performance guarantees has recently arisen from
algorithmizations of the Lov\'{a}sz Local Lemma (LLL), a non-constructive tool
for proving the existence of satisfying states by introducing a background
measure on the state space. While powerful, the state transitions of algorithms
in this class must be, in a precise sense, perfectly compatible with the
background measure. In many applications this is a very restrictive requirement
and one needs to step outside the class. Here we introduce the notion of
\emph{measure distortion} and develop a framework for analyzing arbitrary
focused stochastic local search algorithms, recovering LLL algorithmizations as
the special case of no distortion. Our framework takes as input an arbitrary
such algorithm and an arbitrary probability measure and shows how to use the
measure as a yardstick of algorithmic progress, even for algorithms designed
independently of the measure.
