This paper presents an Improved Bayesian Optimization (IBO) algorithm to solve complex high-dimensional epidemic models' optimal control solution. Evaluating the total objective function value for disease control models with hundreds of thousands of control time periods is a high computational cost. In this paper, we improve the conventional Bayesian Optimization (BO) approach from two parts. The existing BO methods optimize the minimizer step for once time during each acquisition function update process. To find a better solution for each acquisition function update, we do more local minimization steps to tune the algorithm. When the model is high dimensions, and the objective function is complicated, only some update iterations of the acquisition function may not find the global optimal solution. The IBO algorithm adds a series of Adam-based steps at the final stage of the algorithm to increase the solution's accuracy. Comparative simulation experiments using different kernel functions and acquisition functions have shown that the Improved Bayesian Optimization algorithm is effective and suitable for handing large-scale and complex epidemic models under study. The IBO algorithm is then compared with four other global optimization algorithms on three well-known synthetic test functions. The effectiveness and robustness of the IBO algorithm are also demonstrated through some simulation experiments to compare with the Particle Swarm Optimization algorithm and Random Search algorithm. With its reliable convergence behaviors and straightforward implementation, the IBO algorithm has a great potential to solve other complex optimal control problems with high dimensionality.
相關內容
When humans collaborate with each other, they often make decisions by observing others and considering the consequences that their actions may have on the entire team, instead of greedily doing what is best for just themselves. We would like our AI agents to effectively collaborate in a similar way by capturing a model of their partners. In this work, we propose and analyze a decentralized Multi-Armed Bandit (MAB) problem with coupled rewards as an abstraction of more general multi-agent collaboration. We demonstrate that na\"ive extensions of single-agent optimal MAB algorithms fail when applied for decentralized bandit teams. Instead, we propose a Partner-Aware strategy for joint sequential decision-making that extends the well-known single-agent Upper Confidence Bound algorithm. We analytically show that our proposed strategy achieves logarithmic regret, and provide extensive experiments involving human-AI and human-robot collaboration to validate our theoretical findings. Our results show that the proposed partner-aware strategy outperforms other known methods, and our human subject studies suggest humans prefer to collaborate with AI agents implementing our partner-aware strategy.
Complex valued systems with an indefinite matrix term arise in important applications such as for certain time-harmonic partial differential equations such as the Maxwell's equation and for the Helmholtz equation. Complex systems with symmetric positive definite matrices can be solved readily by rewriting the complex matrix system in two-by-two block matrix form with real matrices which can be efficiently solved by iteration using the preconditioned square block (PRESB) preconditioning method and preferably accelerated by the Chebyshev method. The appearances of an indefinite matrix term causes however some difficulties. To handle this we propose different forms of matrix splitting methods, with or without any parameters involved. A matrix spectral analyses is presented followed by extensive numerical comparisons of various forms of the methods.
We discuss estimating the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., $\mathbb{P}(\sum_{i=1}^{N}{X_i} \leq \gamma)$, via importance sampling (IS). We are particularly interested in the rare event regime when $N$ is large and/or $\gamma$ is small. The exponential twisting is a popular technique for similar problems that, in most cases, compares favorably to other estimators. However, it has some limitations: i) it assumes the knowledge of the moment generating function of $X_i$ and ii) sampling under the new IS PDF is not straightforward and might be expensive. The aim of this work is to propose an alternative IS PDF that approximately yields, for certain classes of distributions and in the rare event regime, at least the same performance as the exponential twisting technique and, at the same time, does not introduce serious limitations. The first class includes distributions whose probability density functions (PDFs) are asymptotically equivalent, as $x \rightarrow 0$, to $bx^{p}$, for $p>-1$ and $b>0$. For this class of distributions, the Gamma IS PDF with appropriately chosen parameters retrieves approximately, in the rare event regime corresponding to small values of $\gamma$ and/or large values of $N$, the same performance of the estimator based on the use of the exponential twisting technique. In the second class, we consider the Log-normal setting, whose PDF at zero vanishes faster than any polynomial, and we show numerically that a Gamma IS PDF with optimized parameters clearly outperforms the exponential twisting IS PDF. Numerical experiments validate the efficiency of the proposed estimator in delivering a highly accurate estimate in the regime of large $N$ and/or small $\gamma$.
We propose a Jacobi-style distributed algorithm to solve convex, quadratically constrained quadratic programs (QCQPs), which arise from a broad range of applications. While small to medium-sized convex QCQPs can be solved efficiently by interior-point algorithms, large-scale problems pose significant challenges to traditional algorithms that are mainly designed to be implemented on a single computing unit. The exploding volume of data (and hence, the problem size), however, may overwhelm any such units. In this paper, we propose a distributed algorithm for general, non-separable, large-scale convex QCQPs, using a novel idea of predictor-corrector primal-dual update with an adaptive step size. The algorithm enables distributed storage of data as well as parallel distributed computing. We establish the conditions for the proposed algorithm to converge to a global optimum, and implement our algorithm on a computer cluster with multiple nodes using Message Passing Interface (MPI). The numerical experiments are conducted on data sets of various scales from different applications, and the results show that our algorithm exhibits favorable scalability for solving large-scale problems.
In this paper, we establish the almost sure convergence of two-timescale stochastic gradient descent algorithms in continuous time under general noise and stability conditions, extending well known results in discrete time. We analyse algorithms with additive noise and those with non-additive noise. In the non-additive case, our analysis is carried out under the assumption that the noise is a continuous-time Markov process, controlled by the algorithm states. The algorithms we consider can be applied to a broad class of bilevel optimisation problems. We study one such problem in detail, namely, the problem of joint online parameter estimation and optimal sensor placement for a partially observed diffusion process. We demonstrate how this can be formulated as a bilevel optimisation problem, and propose a solution in the form of a continuous-time, two-timescale, stochastic gradient descent algorithm. Furthermore, under suitable conditions on the latent signal, the filter, and the filter derivatives, we establish almost sure convergence of the online parameter estimates and optimal sensor placements to the stationary points of the asymptotic log-likelihood and asymptotic filter covariance, respectively. We also provide numerical examples, illustrating the application of the proposed methodology to a partially observed Bene\v{s} equation, and a partially observed stochastic advection-diffusion equation.
We consider the least-squares finite element method (lsfem) for systems of nonlinear ordinary differential equations and establish an optimal error estimate for this method when piecewise linear elements are used. The main assumptions are that the vector field is sufficiently smooth and that the local Lipschitz constant, as well as the operator norm of the Jacobian matrix associated with the nonlinearity, are sufficiently small when restricted to a suitable neighborhood of the true solution for the considered initial value problem. This theoretic optimality is further illustrated numerically, along with evidence of possible extension to higher-order basis elements. Examples are also presented to show the advantages of lsfem compared with finite difference methods in various scenarios. Suitable modifications for adaptive time-stepping are discussed as well.
Stochastic Gradient Algorithms (SGAs) are ubiquitous in computational statistics, machine learning and optimisation. Recent years have brought an influx of interest in SGAs, and the non-asymptotic analysis of their bias is by now well-developed. However, relatively little is known about the optimal choice of the random approximation (e.g mini-batching) of the gradient in SGAs as this relies on the analysis of the variance and is problem specific. While there have been numerous attempts to reduce the variance of SGAs, these typically exploit a particular structure of the sampled distribution by requiring a priori knowledge of its density's mode. It is thus unclear how to adapt such algorithms to non-log-concave settings. In this paper, we construct a Multi-index Antithetic Stochastic Gradient Algorithm (MASGA) whose implementation is independent of the structure of the target measure and which achieves performance on par with Monte Carlo estimators that have access to unbiased samples from the distribution of interest. In other words, MASGA is an optimal estimator from the mean square error-computational cost perspective within the class of Monte Carlo estimators. We prove this fact rigorously for log-concave settings and verify it numerically for some examples where the log-concavity assumption is not satisfied.
In the context of epidemiology, policies for disease control are often devised through a mixture of intuition and brute-force, whereby the set of logically conceivable policies is narrowed down to a small family described by a few parameters, following which linearization or grid search is used to identify the optimal policy within the set. This scheme runs the risk of leaving out more complex (and perhaps counter-intuitive) policies for disease control that could tackle the disease more efficiently. In this article, we use techniques from convex optimization theory and machine learning to conduct optimizations over disease policies described by hundreds of parameters. In contrast to past approaches for policy optimization based on control theory, our framework can deal with arbitrary uncertainties on the initial conditions and model parameters controlling the spread of the disease, and stochastic models. In addition, our methods allow for optimization over policies which remain constant over weekly periods, specified by either continuous or discrete (e.g.: lockdown on/off) government measures. We illustrate our approach by minimizing the total time required to eradicate COVID-19 within the Susceptible-Exposed-Infected-Recovered (SEIR) model proposed by Kissler \emph{et al.} (March, 2020).
With the rapid increase of valuable observational, experimental and simulated data for complex systems, much efforts have been devoted to identifying governing laws underlying the evolution of these systems. Despite the wide applications of non-Gaussian fluctuations in numerous physical phenomena, the data-driven approaches to extract stochastic dynamical systems with (non-Gaussian) L\'evy noise are relatively few so far. In this work, we propose a data-driven method to extract stochastic dynamical systems with $\alpha$-stable L\'evy noise from short burst data based on the properties of $\alpha$-stable distributions. More specifically, we first estimate the L\'evy jump measure and noise intensity via computing mean and variance of the amplitude of the increment of the sample paths. Then we approximate the drift coefficient by combining nonlocal Kramers-Moyal formulas with normalizing flows. Numerical experiments on one- and two-dimensional prototypical examples illustrate the accuracy and effectiveness of our method. This approach will become an effective scientific tool in discovering stochastic governing laws of complex phenomena and understanding dynamical behaviors under non-Gaussian fluctuations.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known randomized online coordinate descent algorithms. Furthermore, the proposed algorithms for stochastic optimization exhibit as good convergence rates as the best known randomized coordinate descent algorithms. We also show simulation results to demonstrate performance of the proposed algorithms.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191