Data-Mining Assisted Coarse-Grained Optimization

The design of complex engineering systems usually leads to high-dimensional optimization
problems, where the objective function is expensive to evaluate and may possess a rugged
surface due to the presence of multiple local minima. In such cases gradient-based minimiza-
tion methods won’t be able to locate the global minima unless very specific initial conditions
are chosen. We assume that some ”coarse relaxation” of the objective function is smooth and
we can use this underlying structure to perform coarse-grained optimization. We show that
short runs of a stochastic optimization method, Simulated Annealing [1] can be described by
an effective stochastic differential equation (SDE). Using appropriate subsampling we can
estimate the drift and diffusion coefficients of this SDE [2] and extract information about
the coarse gradient to speed up the ”dynamics” of the optimization method. In addition,
we show that if the data lies on a low-dimensional hyperplane in the parameter space, we
can uncover it using data mining techniques such as PCA or diffusion maps [3], making the
exploration of the objective function surface even more efficient.

References

[1] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,”
Science, vol. 220, no. 4598, pp. 671–680, 1983.

[2] G. A. Pavliotis and A. M. Stuart, “Parameter Estimation for Multiscale Diffusions,”
Journal of Statistical Physics, vol. 127, pp. 741–781, mar 2007.

[3] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W.
Zucker, “Geometric diffusions as a tool for harmonic analysis and structure definition of
data: diffusion maps.,” Proceedings of the National Academy of Sciences of the United
States of America, vol. 102, pp. 7426–31, may 2005.