# Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving
## 2 Methods
### Modified Lam  
At the heart of our approach is an existing adaptive annealing schedule known as the Modified Lam. The Modified Lam is based on the empirical work of [PERSON] and [PERSON] [32], where they studied the behavior of SA over a variety of optimization problems, and observed that during optimal runs the rate at which SA chooses to keep neighboring solutions tends to follow a common trajectory. Specifically, at the beginning of an optimal run, SA accepts nearly all neighbors, but the acceptance rate declines rapidly during the first 15% of the run when it settles upon an acceptance rate of 44%, which it maintains for the next 50% of the run. During the last 35% of the run, the acceptance rate rapidly declines as it converges to a solution. They found that this acceptance rate trajectory effectively balances the trade-off between exploring the search-space and exploiting observed regions of better-quality solutions. The optimal runs under observation are prohibitively long to be of practical use. However, [PERSON] and [PERSON] went a step further and used their observations to derive an adaptive SA that attempts to replicate the acceptance rate behavior of an optimal run, but for a run of predetermined length. [PERSON] and [PERSON]'s approach decreases the temperature monotonically, similar to classic annealing schedules, but uses a variable-sized neighborhood. During the run, if the current acceptance rate is below the target rate, they increase the size of the neighborhood; while if it is above the target rate, they decrease the size of the neighborhood. One of the main drawbacks of [PERSON] and [PERSON]'s [32] approach is the practicality of defining the neighborhood of a solution in a way that enables easily changing its size. This lead [PERSON] to an alternative approach to matching the idealized target rate of acceptance. [PERSON] suggested keeping the neighborhood function fixed, and allowing the temperature to fluctuate both up and down (rather than strictly decreasing) in order to attempt to match the target acceptance rate [31]. [PERSON] later provided a practical instantiation of what is now the Modified Lam [30]. [PERSON]'s Modified Lam requires the run length (in number of SA iterations) as an input. The Modified Lam then defines the target acceptance rate for iteration \(i\), and for an SA run \(N\) iterations in length, as follows:  
\[\text{LamRate}(i)= \begin{cases}0.44+0.56\cdot 560^{-i/(0.15N)}&\text{if }i\leq 0.15N \\ 0.44&\text{if }0.15N<i\leq 0.65N\\ 0.44\cdot 440^{-(i/N-0.65)/0.35}&\text{if }i>0.65N.\end{cases}  \tag{1}\]This leads to exponentially declining acceptance rates for the first 15% and the final 35% of the run, and a constant acceptance rate of 0.44 for the other 50% of the run. This Lam target acceptance rate is shown in Figure 1.  
[PERSON]'s Modified Lam estimates the actual acceptance rate throughout the run using an Exponential Moving Average as follows (\(i\) again is the iteration number):  
\[\text{AcceptRate}(i)= \begin{cases}0.998\cdot\text{AcceptRate}(i-1)+0.002& \text{if neighbor accepted}\\ 0.998\cdot\text{AcceptRate}(i-1)&\text{if neighbor not accepted},\end{cases}  \tag{2}\]  
and where \(\text{AcceptRate}(0)=0.5\). The initial temperature \(T_{0}=0.5\), and the temperature \(T_{i}\) is updated during iteration \(i\) depending upon whether the estimated acceptance rate is higher or lower than the target rate as follows:  
\[T_{i}= \begin{cases}0.999T_{i-1}&\text{if AcceptRate}(i)>\text{LamRate}(i)\\ T_{i-1}/0.999&\text{otherwise}.\end{cases}  \tag{3}\]  
Recently, [PERSON] made some further enhancements, including incremental calculation of the \(\text{LamRate}(i)\) for iteration \(i\) from that of iteration \(i-1\), into what he called the Optimized Modified Lam [25], which is shown in pseudocode form in Algorithm 2.