Optimal Scaling of an Algorithmic Parameter in Restart Strategies

This paper investigates restart strategies for algorithms whose success depends on an algorithmic parameter. It is assumed that there exists a unique unknown optimal. After each restart is increased. The main question is whether there is an optimal strategy for choosing after each restart. To this end, possible restart strategies are classified into parameter-dependent strategy types. A loss function is introduced, that measures the wasted computational costs compared to the optimal strategy. One criterion that a viable restart strategy must satisfy is that the loss relative to the optimal is bounded. Experimental evidence demonstrates that this is not the case for all strategy types. However, for a specific strategy type, where the parameter is increased multiplicatively with an increasing constant, the relative loss function has an upper bound. It will be shown, that for this strategy type there is an optimal choice for the parameter that is independent of the optimal.