Terminating the Algorithm

When we check the tail of logger.csv file in Logging and Post-Processing, we realize that the iteration count, \(k\), is at 100. It is not a coincidence; in polo, the default termination criterion is to have “100 iterations.” Just as most parts of the algorithm, the termination criterion can also be easily changed, or even replaced by a custom terminator. To demonstrate this, we revisit the example in Listing 3, and change the default terminator to a value terminator, which terminates the algorithm if the change in the loss value satisfies certain conditions (see Listing 5).

Listing 5 getting-started/terminator.cpp

/* include system libraries */
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

/* include polo */
#include <polo/polo.hpp>
using namespace polo;

int main(int argc, char *argv[]) {
  /* define the problem data */
  auto data =
      utility::reader<double, int>::svm({"../data/australian_scale"}, 690, 14);

  /* define the smooth loss */
  loss::logistic<double, int> loss(data);

  /* estimate smoothness of the loss */
  double rowmax{0};
  for (int row = 0; row < data.nsamples(); row++) {
    double rowsquare{0};
    for (const auto val : data.matrix()->getrow(row))
      rowsquare += val * val;
    if (rowsquare > rowmax)
      rowmax = rowsquare;
  }
  const double L = 0.25 * data.nsamples() * rowmax;

  /* select and configure the desired solver */
  algorithm::gd<double, int> alg;
  alg.step_parameters(2 / L);

  /* pick a state logger */
  utility::logger::value<double, int> logger;

  /* pick a terminator */
  terminator::value<double, int> terminator(1E-3, 1E-8);

  /* provide an initial vector to the solver, and solve the problem */
  const vector<double> x0(data.nfeatures());
  alg.initialize(x0);
  alg.solve(loss, logger, terminator);

  /* open a csv file for writing */
  ofstream file("terminator.csv");
  if (file) { /* if successfully opened for writing */
    file << "k,t,f\n";
    for (const auto &log : logger)
      file << fixed << log.getk() << ',' << log.gett() << ',' << log.getf()
           << '\n';
  }

  /* print the result */
  cout << "Optimum: " << fixed << alg.getf() << '\n';
  cout << "Optimizer: [";
  for (const auto val : alg.getx())
    cout << val << ',';
  cout << "].\n";

  return 0;
}

In this example, we first construct a value terminator with absolute and relative tolerances of 1E-3 and 1E-8, respectively. This means that terminator will stop the algorithm when

\[{\left\lvert\operatorname{f}\left(x_{k-1}\right) - \operatorname{f}\left(x_{k}\right)\right\rvert} < \delta_{\text{abs}} = 10^{-3} \quad \text{or} \quad {\left\lvert\frac{\operatorname{f}\left(x_{k-1}\right) - \operatorname{f}\left(x_{k}\right)}{\operatorname{f}\left(x_{k-1}\right) + \epsilon}\right\rvert} < \delta_{\text{rel}} = 10^{-8} \,,\]

where \(\epsilon\) is, by default, the machine epsilon, and is used to prevent dividing by zero 1. Then, we provide terminator to the solve method of our algorithm as the third argument. Finally, compared to Listing 3, we change how the function values are logged to terminator.csv and output to cout in Listing 5. In the code, we use std::fixed to print floating-point numbers in a fixed, 6-digit precision (default) format, and getk, gett and getf member functions of log 2 to get the iteration count, wall-clock time and the loss value of each logged iteration of the algorithm.

We append the following lines to CMakeLists.txt

add_executable(terminator terminator.cpp)
target_link_libraries(terminator polo::polo)

and build the project. Running the executable should give the output:

Optimum: 222.288758
Optimizer: [0.042932,0.140170,-0.352319,0.907892,1.224258,0.230179,0.558908,1.755445,0.474237,0.592185,-0.117172,0.669261,-2.293000,1.374797,].

In this example, we realize that the “optimum” (i.e., loss value at the last iterate when the algorithm is stopped by the terminator) is lower than the one obtained in Logging and Post-Processing. When we check the tail of terminator.csv, we observe the following:

1307,52.607826,222.293771
1308,52.645069,222.292765
1309,52.680067,222.291760
1310,52.715353,222.290757
1311,52.751290,222.289757

The algorithm stops at the \(1312^{\text{th}}\) iteration because the absolute change in the loss value becomes less than the tolerance we have asked for. Using the Python script in Listing 6, we obtain a figure similar to Fig. 2.

Listing 6 getting-started/terminator.py

import csv  # for reading a csv file
from matplotlib import pyplot as plt  # for plotting

k = []
t = []
f = []

with open("terminator.csv") as csvfile:
    csvReader = csv.reader(csvfile, delimiter=",")
    next(csvReader)  # skip the header
    for row in csvReader:
        k.append(int(row[0]))
        t.append(float(row[1]))
        f.append(float(row[2]))

h, w = plt.figaspect(0.5)
fig, axes = plt.subplots(1, 2, sharey=True, figsize=(h, w))

# f vs k
axes[0].plot(k, f)
axes[0].set_xlabel(r"$k$")
axes[0].set_ylabel(r"$f(\cdot)$")
axes[0].grid()

# f vs t
axes[1].plot(t, f)
axes[1].set_xlabel(r"$t$ [ms]")
axes[1].grid()

plt.tight_layout()
plt.savefig("terminator.svg")
plt.savefig("terminator.pdf")

Fig. 2 Loss values generated by the algorithm in Listing 5.

In Fig. 2, we observe that the value terminator with the selected tolerances has resulted in more than 12 times more iterations (left) compared to the default iteration terminator with 100 iterations. Because we run both algorithms serially using one CPU, this directly translates to the wall-clock runtimes (right) of the algorithms (cf. Fig. 1).

Footnotes

1

More information on terminators is provided in Algorithm Terminators.

2

More information on state loggers and their logged data is provided in State Loggers.