Modify Stopping Criterion

[vivekaxl]

Related to #451
Is there any way to set stopping criterion policies? For example, if the incumbent does not change for five consecutive iterations, then terminate.

[vivekaxl]

I modified ./smac/optimizer/smbo.py (of the smac library) to add a new stopping criterion.

    def run(self):
        """Runs the Bayesian optimization loop

        Returns
        ----------
        incumbent: np.array(1, H)
            The best found configuration
        """
        self.start()

       # + stopping.criterion
        lives = 5
       # - stopping.criterion

        # Main BO loop
        while True:
            if self.scenario.shared_model:
                pSMAC.read(run_history=self.runhistory,
                           output_dirs=self.scenario.input_psmac_dirs,
                           configuration_space=self.config_space,
                           logger=self.logger)

            start_time = time.time()
            X, Y = self.rh2EPM.transform(self.runhistory)

            self.logger.debug("Search for next configuration")
            # get all found configurations sorted according to acq
            challengers = self.choose_next(X, Y)

            time_spent = time.time() - start_time
            time_left = self._get_timebound_for_intensification(time_spent)

            self.logger.debug("Intensify")

            # + stopping.criterion
            prev = self.incumbent
            # - stopping.criterion

            self.incumbent, inc_perf = self.intensifier.intensify(
                challengers=challengers,
                incumbent=self.incumbent,
                run_history=self.runhistory,
                aggregate_func=self.aggregate_func,
                time_bound=max(self.intensifier._min_time, time_left))

            if self.scenario.shared_model:
                pSMAC.write(run_history=self.runhistory,
                            output_directory=self.scenario.output_dir_for_this_run)

            logging.debug("Remaining budget: %f (wallclock), %f (ta costs), %f (target runs)" % (
                self.stats.get_remaing_time_budget(),
                self.stats.get_remaining_ta_budget(),
                self.stats.get_remaining_ta_runs()))

            # + stopping.criterion
            if prev == self.incumbent:
                lives -= 1
           
            if self.stats.is_budget_exhausted() or lives==0:
                break
            # - stopping.criterion

            self.stats.print_stats(debug_out=True)
        return self.incumbent

What do you think?

[mlindauer]

Hi Vivek,

Thanks for the idea.

Two comments:

1. SMAC would stop even if we saw 5 non-improving iterations that are not consecutive. I think a reset of lives=5 is missing.
2. My guess would be that SMAC will perform terrible on some benchmarks with this termination criterion. For example, if it is very unlikely to perform better than the default configuration (i.e., the region of fairly small compared to the entire search space), SMAC will need many iterations before it will stumble upon the better region and only afterwards, it start to improve the performance of the target algorithm. In fact, most of our algorithm configuration benchmarks have such a characteristic.

[vivekaxl]

SMAC would stop even if we saw 5 non-improving iterations that are not consecutive. I think a reset of lives=5 is missing.

Yes, you are correct.

My guess would be that SMAC will perform terribly on some benchmarks with this termination criterion.

In the case study that I am using, it has been shown by prior work that an Evolutionary algorithm can find a good configuration with similar stopping criterion---hence wanted to try it out. However, in more general cases, I agree with what you said.

[mlindauer]

In the case study that I am using, it has been shown by prior work that an Evolutionary algorithm can find a good configuration with similar stopping criterion

What was the population size of the EA?
Please note that SMAC will only evaluate two configurations in early iterations (i.e., each iteration consists of one configurations based on EI and one randomly sampled).

[vivekaxl]

The population size of the EA is 10 and the max iteration is 10. It has a very strict stopping criterion. The EA would terminate if the value of the incumbent (best of the generation) does not change for 5 generation (does not have to be consecutive).

I do agree with your point that lives=5 in the EA setup does not translate to lives=5 in SMAC. I am currently thinking how we can do apples to apple comparison between the EA and autosklearn. Suggestions are welcome.

[mlindauer]

You could try to force SMAC to run 5 configurations in each iteration.
Unfortunately, this is not an option exposed to users. So you have to change one line in the code:
https://github.com/automl/SMAC3/blob/master/smac/intensification/intensification.py#L105

@mfeurer should know whether this has some other implications for auto-sklearn (that I'm not aware of).

[mfeurer]

I wouldn't know of any implications for Auto-sklearn if you run at least 5 configurations in each iteration except that the EI optimization in SMAC isn't built for that.

Besides that I'm wondering why the number of iterations without improvement is a good criterion in general to stop the search when using a global optimization algorithm. Are there any theoretical reasons or is this rather an EA-community thing?

[mfeurer]

Closing this as there is no clear TODO here and this could be better achieved with callbacks (which are not implemented yet, but probably should be as requested by #1100).