# Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving
## 1 Introduction
The component of SA that controls the change of temperature is known as the annealing schedule, and there are several common annealing schedules such as exponential cooling (\(f(T)=\alpha\cdot T\), where \(\alpha\in[0.0,1.0]\) is a cooling rate less than, but usually near, 1.0, such as 0.95), linear cooling (\(f(T)=T-\lambda\), where \(\lambda\) is a parameter), and logarithmic cooling (\(f_{i}(T)=c/\ln(i+d)\), where \(i\) is the iteration number, and \(c\) and \(d\) are parameters). All of these start the temperature at some initially \"high\" value \(T_{0}\) (line 7 of Algorithm 1) and then monotonically decrease it during the run. However, what qualifies as \"high\", and how quickly the temperature should decrease (values for the hyperparameters, \(\alpha\), \(\lambda\), \(c\), \(d\) of the various annealing schedules), may vary from one problem to another, and perhaps even from one instance to another. Good choices for these also likely depends upon the amount of time you have available to solve your problem. If you have much time available, then you might start with a higher temperature, and use a slower rate of cooling, than you would if you had very little time available. If you utilize one of these classic annealing schedules, then you will need to tune the hyperparameters ahead of time in some way using problem instances representative of the instances that you expect to encounter for your application. However, if the assumptions that you make about expected future instances vary much from what you actually later encounter in practice, then your SA may perform significantly below its capability. As an alternative to one of the classic annealing schedules, several researchers have developed adaptive annealing schedules [25; 26; 27; 28; 29; 30; 31; 32], imparting upon SA the ability to self-adjustthe temperature during the run utilizing problem solving feedback to learn to improve performance. A recent example is [PERSON]'s hybrid of an adaptive SA with expectation-maximization for inference in hidden Markov models [26]. Another example is the approach by [PERSON] et al, which accelerates the rate of cooling as the temperature decreases [29]. [PERSON] observed that many adaptive annealing schedules assume that you at least know how much time is available for the run, but if that assumption is incorrect then SA may either spend too much time in a random walk (e.g., if much less time is available than you thought), or converge too quickly to local optima (e.g., if much more time is available than you thought). This observation leads [PERSON] to introduce an approach that adapts the run length of SA over the course of a sequence of restarts, both in the sequential case as well as for a parallel SA [27]. [PERSON] and [PERSON]'s early work on adaptive simulated annealing dynamically adjusts the size of the neighborhood function to attempt to follow a theoretically determined trajectory of the rate of neighbor acceptance, while using a monotonically decreasing temperature [32]. This has become known as Lam annealing. [PERSON] later modified [PERSON] and [PERSON]'s approach to keep the neighborhood function fixed, and instead allows the temperature to fluctuate up and down throughout the run as necessary in order to keep the SA run on the acceptance rate trajectory of [PERSON] and [PERSON]'s approach [31]. [PERSON] refined [PERSON]'s approach into what is now known as the Modified Lam [30], and which was then later further optimized by [PERSON] [25]. We provide complete algorithmic details of the Modified Lam in Section 2.1 since it forms the foundation of our approach. Our primary contribution is a new adaptive annealing schedule that we call the Self-Tuning Lam. The Self-Tuning Lam builds upon the Modified Lam, and is designed to overcome its limitations. The Modified Lam is often described as parameter-free [33]. However, it has several constants, whose values are argued to suffice across most problems.