# American Institute of Mathematical Sciences

December  2020, 7(2): 511-536. doi: 10.3934/jcd.2020021

## Manifold learning for accelerating coarse-grained optimization

 1 Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ 08544, USA 2 Department of Applied Mathematics and Statistics (AMS), Johns Hopkins University, Baltimore, MD 21218, USA 3 Department of Mathematics, Imperial College London, London SW7 2AZ, UK 4 Department of Chemical and Biomolecular Engineering & AMS, Johns Hopkins University, Baltimore, MD 21218, USA

* Corresponding author

Received  October 2019 Published  July 2020

Algorithms proposed for solving high-dimensional optimization problems with no derivative information frequently encounter the "curse of dimensionality, " becoming ineffective as the dimension of the parameter space grows. One feature of a subclass of such problems that are effectively low-dimensional is that only a few parameters (or combinations thereof) are important for the optimization and must be explored in detail. Knowing these parameters/combinations in advance would greatly simplify the problem and its solution. We propose the data-driven construction of an effective (coarse-grained, "trend") optimizer, based on data obtained from ensembles of brief simulation bursts with an "inner" optimization algorithm, that has the potential to accelerate the exploration of the parameter space. The trajectories of this "effective optimizer" quickly become attracted onto a slow manifold parameterized by the few relevant parameter combinations. We obtain the parameterization of this low-dimensional, effective optimization manifold on the fly using data mining/manifold learning techniques on the results of simulation (inner optimizer iteration) burst ensembles and exploit it locally to "jump" forward along this manifold. As a result, we can bias the exploration of the parameter space towards the few, important directions and, through this "wrapper algorithm, " speed up the convergence of traditional optimization algorithms.

Citation: Dmitry Pozharskiy, Noah J. Wichrowski, Andrew B. Duncan, Grigorios A. Pavliotis, Ioannis G. Kevrekidis. Manifold learning for accelerating coarse-grained optimization. Journal of Computational Dynamics, 2020, 7 (2) : 511-536. doi: 10.3934/jcd.2020021
##### References:

show all references

##### References:
Evolution in time of the probability density of current points using either the Langevin equation or SA at constant $T$. The objective function is $f(x) = 0.5x^2$; $10^4$ realizations are used with starting point $x = 1$, $T = 0.5$; and the time step is $dt = 10^{-3}$
Applying Diffusion Maps to the Swiss roll data set
One complete run of the algorithm that approaches the global maximum. Six total "coarse iterations" (shown in red) were performed. In addition, a single run of SA using the same number of function evaluations is shown in green. Our algorithm visibly approaches the maximum much faster
A comparison of the evolving maximum objective value for both methods. SA combined with DMaps needs only a fraction of the total function evaluations compared to simple SA
Diffusion Maps applied to bursts on a rectangular strip]{Diffusion maps applied to (A) the original 2D data with Euclidean distances, and (B) the transformed data with Mahalanobis distances. In both cases, the inherent dimensionality is recovered in the first two eigenvectors, as the coloring of the data by the leading Diffusion Map coordinates corresponding to these two eigenvectors show
Estimation of the first drift coefficient $\theta_1$. "Theoretical" are obtained numerically from (5), "Euclidean" via DMaps on the original data, and "Mahalanobis" from DMaps on the transformed data. The last subplot shows results from Euclidean DMaps on transformed data, which, as expected, yields incorrect estimates
Estimation of the second drift coefficient $\theta_2$. The subplots are analogous to those in Figure 6
Coarse-grained (two-dimensional) optimization on a cylindrical surface in three dimensions. One complete run of the algorithm, illustrating the short bursts of trajectories and new points after being lifted by geometric harmonics. Observe that, although the lifting does not perfectly locate the cylinder, the burst trajectories are quickly attracted back to it. The second plot is a top-down view of the first
Simulation of a short trajectory initialized at perturbed initial conditions $(x_{ic}, \bf{y}_{ic})$
The first diffusion coordinate parameterizes $x$
Estimation of the drift coefficient in diffusion map space
Estimation of the diffusion coefficient in diffusion map space
Nonlinear transformation of the slow variable $x$ onto a semicircle in the plane
Embeddings of the original and transformed data set
Estimation of the drift coefficient in Diffusion Map space
Estimation of the diffusion coefficient in Diffusion Map space
Estimation of the drift coefficient in diffusion map space
Estimation of the diffusion coefficient in diffusion map space
 [1] S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435 [2] Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319 [3] Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217 [4] Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117 [5] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [6] Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $p$ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442 [7] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [8] Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032 [9] Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316 [10] Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321 [11] Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458 [12] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [13] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [14] H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433 [15] Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242 [16] Hai-Feng Huo, Shi-Ke Hu, Hong Xiang. Traveling wave solution for a diffusion SEIR epidemic model with self-protection and treatment. Electronic Research Archive, , () : -. doi: 10.3934/era.2020118 [17] Peter Poláčik, Pavol Quittner. Entire and ancient solutions of a supercritical semilinear heat equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 413-438. doi: 10.3934/dcds.2020136 [18] Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345 [19] Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384 [20] Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

Impact Factor: