Online EM Algorithm for Hidden Markov Models

Online (also called “recursive” or “adaptive”) estimation of fixed model parameters in hidden Markov models is a topic of much interest in times series modeling. In this work, we propose an online parameter estimation algorithm that combines two key ideas. The first one, which is deeply rooted in the Expectation-Maximization (EM) methodology, consists in reparameterizing the problem using complete-data sufficient statistics. The second ingredient consists in exploiting a purely recursive form of smoothing in HMMs based on an auxiliary recursion. Although the proposed online EM algorithm resembles a classical stochastic approximation (or Robbins–Monro) algorithm, it is sufficiently different to resist conventional analysis of convergence. We thus provide limited results which identify the potential limiting points of the recursion as well as the large-sample behavior of the quantities involved in the algorithm. The performance of the proposed algorithm is numerically evaluated through simulations in the case of a noisily observed Markov chain. In this case, the algorithm reaches estimation results that are comparable to those of the maximum likelihood estimator for large sample sizes. The supplemental material for this article available online includes an appendix with the proofs of Theorem 1 and Corollary 1 stated in Section 4 as well as the MATLAB/OCTAVE code used to implement the algorithm in the case of a noisily observed Markov chain considered in Section 5.     

Stochastic Approximation Algorithms for Parameter Estimation in Option Pricing with Regime Switching

Abstract

This work is concerned with option pricing. Stochastic approximation/optimization algorithms are proposed and analyzed. The underlying stock price evolves according to two geometric Brownian motions coupled by a continuous-time finite state Markov chain. Recursive stochastic approximation algorithms are developed to estimate the implied volatility. Convergence of the algorithm is proved. Rate of convergence is also ascertained. Then real market data are used to compare our algorithms with other schemes.     

Optimal Distributed Dynamic Advertising

We propose a novel approach to modeling advertising dynamics for a firm operating over a distributed market domain based on controlled partial differential equations of the diffusion type. Using our model, we consider a general type of finite-horizon profit maximization problem in a monopoly setting. By reformulating this profit maximization problem as an optimal control problem in infinite dimensions, we derive sufficient conditions for the existence of its optimal solutions under general profit functions, as well as state and control constraints, and provide a general characterization of the optimal solutions. Sharper, feedback-form characterizations of the optimal solutions are obtained for two variants of the general problem. The first author gratefully acknowledges financial support by the NSF, the DAAD, the SFB 611 (Bonn), and the Max-Planck-Institut für Mathematik (Leipzig) through an IPDE fellowship.     

Distributed stochastic nonsmooth nonconvex optimization

Distributed consensus optimization has received considerable attention in recent years and several distributed consensus-based algorithms have been proposed for (nonsmooth) convex and (smooth) nonconvex objective functions. However, the behavior of these distributed algorithms on nonconvex, nonsmooth and stochastic objective functions is not understood. Such class of functions and distributed setting are motivated by several applications, including problems in machine learning and signal processing. This paper presents the first convergence analysis of the decentralized stochastic subgradient method for such classes of problems, over networks modeled as undirected, fixed, graphs.     

Gradient-based simulation optimization under probability constraints

We study optimization problems subject to possible fatal failures. The probability of failure should not exceed a given confidence level. The distribution of the failure event is assumed unknown, but it can be generated via simulation or observation of historical data. Gradient-based simulation-optimization methods pose the difficulty of the estimation of the gradient of the probability constraint under no knowledge of the distribution. In this work we provide two single-path estimators with bias: a convolution method and a finite difference, and we provide a full analysis of convergence of the Arrow-Hurwicz algorithm, which we use as our solver for optimization. Convergence results are used to tune the parameters of the numerical algorithms in order to achieve best convergence rates, and numerical results are included via an example of application in finance.     

Meshfree Approximation for Stochastic Optimal Control Problems

In this work,we study the gradient projection method for solving a class of stochastic control problems by using a mesh free approximation ap-proach to implement spatial dimension approximation.Our main contribu-tion is to extend the existing gradient projection method to moderate high-dimensional space.The moving least square method and the general radial basis function interpolation method are introduced as showcase methods to demonstrate our computational framework,and rigorous numerical analysis is provided to prove the convergence of our meshfree approximation approach.We also present several numerical experiments to validate the theoretical re-sults of our approach and demonstrate the performance meshfree approxima-tion in solving stochastic optimal control problems.     

A smoothing stochastic algorithm for quantile estimation

In this paper, we provide the almost-sure convergence and the asymptotic normality of a smooth version of the Robbins–Monro algorithm for the quantile estimation. A Monte Carlo simulation study shows that our proposed method works well within the framework of a data stream.     

Optimal Scaling of a Gradient Method for Distributed Resource Allocation

We consider a class of weighted gradient methods for distributed resource allocation over a network. Each node of the network is associated with a local variable and a convex cost function; the sum of the variables (resources) across the network is fixed. Starting with a feasible allocation, each node updates its local variable in proportion to the differences between the marginal costs of itself and its neighbors. We focus on how to choose the proportional weights on the edges (scaling factors for the gradient method) to make this distributed algorithm converge and on how to make the convergence as fast as possible.We give sufficient conditions on the edge weights for the algorithm to converge monotonically to the optimal solution; these conditions have the form of a linear matrix inequality. We give some simple, explicit methods to choose the weights that satisfy these conditions. We derive a guaranteed convergence rate for the algorithm and find the weights that minimize this rate by solving a semidefinite program. Finally, we extend the main results to problems with general equality constraints and problems with block separable objective function.The authors are grateful to Professor Paul Tseng and the anonymous referee for their valuable comments that helped us to improve the presentation of this paper.Communicated by P. Tseng     

Recursive parameter estimation: convergence

We consider estimation procedures which are recursive in the sense that each successive estimator is obtained from the previous one by a simple adjustment. We propose a wide class of recursive estimation procedures for the general statistical model and study convergence.      

Observers for Systems with Discrete and Distributed Delays

An observer theory for linear systems containing discrete anddistributed delays in its state- and output equations is presented.In particular, existence criteria for observers with finite-dimensionalerror dynamics are derived. The stabilizability and eigenvalueassignability of the observation error dynamics are expressedin terms of the invariant zeros of a matrix function P(s), dependingon the discrete delay parameters and the parameters of a Gram-Schmidtexpansion of the distributed delay terms.     

A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.     

人口普查质量评估调查中的双系统估计量

在通过问卷获取人口信息的人口普查中,总是存在不同程度的人口多报或漏报,导致普查人口数偏离实际人口数。这就需要对人口普查的质量进行评估。使用文献解读法探讨基于双系统估计量的人口普查净误差估计问题,包括抽样方法、抽样权数、双系统估计量的建立,等等。这有助于我国构建科学适用的以双系统估计量为核心的人口普查质量评估理论方法体系。     

Continuous Contour Monte Carlo for Marginal Density Estimation With an Application to a Spatial Statistical Model

The problem of marginal density estimation for a multivariate density function f(x) can be generally stated as a problem of density function estimation for a random vector λ(x) of dimension lower than that of x. In this article, we propose a technique, the so-called continuous Contour Monte Carlo (CCMC) algorithm, for solving this problem. CCMC can be viewed as a continuous version of the contour Monte Carlo (CMC) algorithm recently proposed in the literature. CCMC abandons the use of sample space partitioning and incorporates the techniques of kernel density estimation into its simulations. CCMC is more general than other marginal density estimation algorithms. First, it works for any density functions, even for those having a rugged or unbalanced energy landscape. Second, it works for any transformation λ(x) regardless of the availability of the analytical form of the inverse transformation. In this article, CCMC is applied to estimate the unknown normalizing constant function for a spatial autologistic model, and the estimate is then used in a Bayesian analysis for the spatial autologistic model in place of the true normalizing constant function. Numerical results on the U.S. cancer mortality data indicate that the Bayesian method can produce much more accurate estimates than the MPLE and MCMLE methods for the parameters of the spatial autologistic model.     

Stationary Distribution and Extinction of Stochastic Beddington-DeAngelis Predator-prey Model with Distributed Delay

In this paper, the formats of Julia sets for a class of nonlinear complex dynamic systems with variable coefficients were studied under certain conditions. For the complex dynamic systems in piecewise cases, we proposed some methods to control the forms of their Julia sets and stable domains analytically. What’s more, we illustrated that our methods worked well by computational simulations. Our work provides a better understanding about how to control the Julia sets of certain complex dynamic systems.     

On martingale limit theory and strong convergence results for stochastic approximation procedures

The analysis of asymptotic behaviour of stochastic approximation procedures rests heavily on the use of martingale limit theory, although explicit recognition of this situation is notable for its absence in the literature. This point is emphasized and in illustration a martingale iterated logarithm result is used to obtain strong convergence results of iterated logarithm type for the basic Robbins–Monro and Kiefer–Wolfowitz procedures.     

A New Estimator for a Tail Index

We investigate properties of a new estimator for a tail index introduced by Davydov and co-workers. The main advantage of this estimator is the simplicity of the statistic used for the estimator. We provide results of simulation by comparing plots of our's and Hill's estimators.     

An Online Expectation–Maximization Algorithm for Changepoint Models

Changepoint models are widely used to model the heterogeneity of sequential data. We present a novel sequential Monte Carlo (SMC) online expectation–maximization (EM) algorithm for estimating the static parameters of such models. The SMC online EM algorithm has a cost per time which is linear in the number of particles and could be particularly important when the data is representable as a long sequence of observations, since it drastically reduces the computational requirements for implementation. We present an asymptotic analysis for the stability of the SMC estimates used in the online EM algorithm and demonstrate the performance of this scheme by using both simulated and real data originating from DNA analysis. The supplementary materials for the article are available online.     

Tracking consensus of nonlinear MASs with asymmetric communication delays in noisy environments

This paper investigates the tracking consensus problem of nonlinear multi-agent systems (MASs) with asymmetric time-varying communication delays in noisy environments under the conditions of fixed and switching directed topologies. A novel stochastic analysis approach is proposed, which guarantees that the designed two distributed tracking protocols can guide the controlled systems to achieve tracking consensus in the sense of mean square. In order to further reveal the influence of asymmetric communication delays on the tracking consensus ability for MASs, some new delay-dependent sufficient conditions for mean-square consensus are also developed. A simple example is finally given to illustrate the effectiveness of the proposed theoretical results.     

Distributed computation of Pareto solutions inn-player games

The problem of computing Pareto optimal solutions with distributed algorithms is considered inn-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.