Markov Chain Analysis of Noise and Restart in Stochastic Local Search

Ole J. Mengshoel, Youssef Ahres, Tong YuIJCAI 2016

Introduction

Stochastic Local Search (SLS) algorithms are fundamental tools in combinatorial optimization, widely applied in fields ranging from hardware verification to Bayesian network inference. These algorithms typically balance "greedy" moves toward local optima with "noise"—random moves intended to escape stagnation. When progress halts, practitioners often employ "hard restarts," resetting the search after a fixed number of steps. While empirically successful, hard restarts introduce non-homogeneity into the search process, as the probability of restarting depends on the time elapsed since the last reset. This dependency complicates standard Markov chain analysis, making it difficult to theoretically predict the "expected hitting time" (the time required to find a solution) or to optimize parameters systematically.

The MarkovSLS Framework

To bridge the gap between empirical success and theoretical understanding, this work introduces MarkovSLS, a generalized framework that replaces deterministic hard restarts with soft restarts. In a soft restart regime, the algorithm has a fixed probability ($p_r$) of restarting at every step. This innovation ensures that the search process remains a homogeneous Markov chain, enabling rigorous mathematical analysis.

The framework supports two primary variants:

  1. SoftSLS: Utilizes fixed probabilities for noise ($p_n$) and restarts ($p_r$). This allows for the exact calculation of expected hitting times using linear algebra.
  2. AdaptiveSLS: Dynamically adjusts $p_n$ and $p_r$ based on search progress. If the algorithm detects stagnation (e.g., frequent self-loops in the state space), it increases these probabilities to facilitate escape from local optima.

Modeling with Deceptive Markov Chains

The authors utilize Deceptive Markov Chains (DMC) to model "tricky" search landscapes characterized by local optima (traps). These 1D representations approximate the high-dimensional spaces encountered in real-world problems.

State transition diagram for a Deceptive Markov Chain (DMC) with $n=5$ states.

As shown in Figure 1, the DMC model explicitly incorporates the probabilities of noise and restart into the transition matrix. The authors prove that a soft restart with probability $p_r$ is functionally equivalent to a hard restart every $1/p_r$ steps in terms of expected restart time, providing a solid theoretical foundation for the soft restart approach.

Analytical Optimization and Results

By modeling the search as a DMC, the authors derived the "optimal" noise and restart probabilities mathematically. They validated these theoretical predictions through extensive simulations on synthetic deceptive functions and real-world feature selection tasks.

Expected hitting times as a function of noise ($P_n$) and restart ($P_r$) probabilities for different problem landscapes.

Figure 3 displays contour plots of expected hitting times across various problem configurations. The dark regions represent the "sweet spots" where the combination of $p_n$ and $p_r$ minimizes search time. The empirical results perfectly matched these theoretical contours, confirming the validity of the Markov chain approach.

Key findings include:

  • Sensitivity of Restart: The restart parameter ($p_r$) is often more critical than noise ($p_n$); minor adjustments in $p_r$ can lead to significant changes in performance.
  • Adaptivity: AdaptiveSLS frequently matched or outperformed the analytically optimized SoftSLS. This suggests that real-time adaptation to the local landscape is highly effective, even without prior knowledge of the global search space.
  • Real-World Performance: On feature selection datasets (e.g., Wine, Diabetes), AdaptiveSLS consistently outperformed standard benchmarks like Simulated Annealing and AdaptiveNoise.

Conclusion

This research demonstrates that soft restarts enable a powerful Markov chain analysis of SLS algorithms. By transforming the search into a homogeneous process, researchers can analytically optimize parameters and develop robust adaptive strategies. While the current analysis relies on simplified 1D models (DMCs), it paves the way for future integration with Markov Decision Processes (MDPs) to create even more sophisticated controllers for high-dimensional optimization problems.

Summary updated

BibTeX
@inproceedings{mengshoel2016markov,
  author = {Ole J. Mengshoel and Youssef Ahres and Tong Yu},
  title = {{Markov Chain Analysis of Noise and Restart in Stochastic Local Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure