More often than not, we cannot directly measure many phenomena that are crucial to us. However, we usually have access to certain partial observations on the phenomena of interest as well as a mathematical model of them. The filtering problem seeks estimation of the phenomena given all the accumulated partial information. In this thesis, we study several topics concerning the numerical approximation of the filtering problem. First, we study the continuous-time filtering problem. Given high-frequency ob- servations in discrete-time, we perform double discretization of the non-linear filter to allow for filter estimation with particle filter. By using the multilevel strategy, given any ε > 0, our algorithm achieve an MSE level of O(ε2) with a cost of O(ε−3), while the particle filter requires a cost of O(ε−4). Second, we propose a de-bias scheme for the particle filter under the partially observed diffusion model. The novel scheme is free of innate particle filter bias and discretization bias, through a double randomization method of [14]. Our estimator is perfectly parallel and achieves a similar cost reduction to the multilevel particle filter. Third, we look at a high-dimensional linear Gaussian state-space model in con- tinuous time. We propose a novel multilevel estimator which requires a cost of O(ε−2 log(ε)2) compared to ensemble Kalman-Bucy filters (EnKBFs) which requiresO(ε−3) for an MSE target of O(ε2). Simulation results verify our theory for models of di- mension ∼ 106. Lastly, we consider the model estimation through learning an unknown parameter that characterizes the partially observed diffusions. We propose algorithms to provide unbiased estimates of the Hessian and the inverse Hessian, which allows second-order optimization parameter learning for the model.

Many key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to cope with these challenges. In this thesis, we deal with each of these sources of difficulty in a different way. To efficiently address the big data issue, we develop new methods which in each iteration examine a small random subset of the training data only. To handle the big model issue, we develop methods which in each iteration update a random subset of the model parameters only. Finally, to deal with ill-conditioned problems, we devise methods that incorporate either higher-order information or Nesterov’s acceleration/momentum. In all cases, randomness is viewed as a powerful algorithmic tool that we tune, both in theory and in experiments, to achieve the best results. Our algorithms have their primary application in training supervised machine learning models via regularized empirical risk minimization, which is the dominant paradigm for training such models. However, due to their generality, our methods can be applied in many other fields, including but not limited to data science, engineering, scientific computing, and statistics.

No description available.

Doctor of Philosophy / Department of Mechanical and Nuclear Engineering / J. Kenneth Shultis / A method for deterministically calculating the population variances of Monte Carlo particle transport calculations involving weight-dependent variance reduction has been developed. This method solves a set of equations developed by Booth and Cashwell [1979], but extends them to consider the weight-window variance reduction technique. Furthermore, equations that calculate the duration of a single history in an MCNP5 (RSICC version 1.51) calculation have been developed as well. The calculation cost, defined as the inverse figure of merit, of a Monte Carlo calculation can be deterministically minimized from calculations of the expected variance and expected calculation time per history.The method has been applied to one- and two-dimensional multi-group and mixed material problems for optimization of weight-window lower bounds. With the adjoint (importance) function as a basis for optimization, an optimization mesh is superimposed on the geometry. Regions of weight-window lower bounds contained within the same optimization mesh element are optimized together with a scaling parameter. Using this additional optimization mesh restricts the size of the optimization problem, thereby eliminating the need to optimize each individual weight-window lower bound. Application of the optimization method to a one-dimensional problem, designed to replicate the variance reduction iron-window effect, obtains a gain in efficiency by a factor of 2 over standard deterministically generated weight windows. The gain in two dimensional problems varies. For a 2-D block problem and a 2-D two-legged duct problem, the efficiency gain is a factor of about 1.2. The top-hat problem sees an efficiency gain of 1.3, while a 2-D 3-legged duct problem sees an efficiency gain of only 1.05. This work represents the first attempt at deterministic optimization of Monte Carlo calculations with weight-dependent variance reduction. However, the current work is limited in the size of problems that can be run by the amount of computer memory available in computational systems. This limitation results primarily from the added discretization of the Monte Carlo particle weight required to perform the weight-dependent analyses. Alternate discretization methods for the Monte Carlo weight should be a topic of future investigation. Furthermore, the accuracy with which the MCNP5 calculation times can be calculated deterministically merits further study.

Monte Carlo sampling-based methods are frequently used in stochastic programming when exact solution is not possible. In this dissertation, we develop two sets of Monte Carlo sampling-based algorithms to solve classes of two-stage stochastic programs. These algorithms follow a sequential framework such that a candidate solution is generated and evaluated at each step. If the solution is of desired quality, then the algorithm stops and outputs the candidate solution along with an approximate (1 - α) confidence interval on its optimality gap. The first set of algorithms proposed, which we refer to as the fixed-width sequential sampling methods, generate a candidate solution by solving a sampling approximation of the original problem. Using an independent sample, a confidence interval is built on the optimality gap of the candidate solution. The procedures stop when the confidence interval width plus an inflation factor falls below a pre-specified tolerance epsilon. We present two variants. The fully sequential procedures use deterministic, non-decreasing sample size schedules, whereas in another variant, the sample size at the next iteration is determined using current statistical estimates. We establish desired asymptotic properties and present computational results. In another set of sequential algorithms, we combine deterministically valid and sampling-based bounds. These algorithms, labeled sampling-based sequential approximation methods, take advantage of certain characteristics of the models such as convexity to generate candidate solutions and deterministic lower bounds through Jensen's inequality. A point estimate on the optimality gap is calculated by generating an upper bound through sampling. The procedure stops when the point estimate on the optimality gap falls below a fraction of its sample standard deviation. We show asymptotically that this algorithm finds a solution with a desired quality tolerance. We present variance reduction techniques and show their effectiveness through an empirical study.

The probability that a sum of random variables (RVs) exceeds (respectively falls below) a given threshold, is often encountered in the performance analysis of wireless communication systems. Generally, a closed-form expression of the sum distribution does not exist and a naive Monte Carlo (MC) simulation is computationally expensive when dealing with rare events. An alternative approach is represented by the use of variance reduction techniques, known for their efficiency in requiring less computations for achieving the same accuracy requirement. For the right-tail region, we develop a unified hazard rate twisting importance sampling (IS) technique that presents the advantage of being logarithmic efficient for arbitrary distributions under the independence assumption. A further improvement of this technique is then developed wherein the twisting is applied only to the components having more impacts on the probability of interest than others. Another challenging problem is when the components are correlated and distributed according to the Log-normal distribution. In this setting, we develop a generalized hybrid IS scheme based on a mean shifting and covariance matrix scaling techniques and we prove that the logarithmic efficiency holds again for two particular instances. We also propose two unified IS approaches to estimate the left-tail of sums of independent positive RVs. The first applies to arbitrary distributions and enjoys the logarithmic efficiency criterion, whereas the second satisfies the bounded relative error criterion under a mild assumption but is only applicable to the case of independent and identically distributed RVs. The left-tail of correlated Log-normal variates is also considered. In fact, we construct an estimator combining an existing mean shifting IS approach with a control variate technique and prove that it possess the asymptotically vanishing relative error property. A further interesting problem is the left-tail estimation of sums of ordered RVs. Two estimators are presented. The first is based on IS and achieves the bounded relative error under a mild assumption. The second is based on conditional MC approach and achieves the bounded relative error property for the Generalized Gamma case and the logarithmic efficiency for the Log-normal case.

Un certain nombre de domaines tels que les études de criticité requièrent le calcul de certaines grandeurs neutroniques d'intérêt. Il existe deux types de code : les codes déterministes et les codes stochastiques. Ces derniers sont réputés simuler la physique de la configuration traitée de manière exacte. Toutefois, le temps de calcul nécessaire peut s'avérer très élevé.Le travail réalisé dans cette thèse a pour but de bâtir une stratégie d'accélération de la convergence de la criticité dans le code de calcul TRIPOLI-4®. Nous souhaitons mettre en œuvre le jeu à variance nulle. Pour ce faire, il est nécessaire de calculer le flux adjoint. L'originalité de cette thèse est de calculer directement le flux adjoint par une simulation directe Monte-Carlo sans passer par un code externe, grâce à la méthode de la matrice de fission. Ce flux adjoint est ensuite utilisé comme carte d'importance afin d'accélérer la convergence de la simulation. / Fields such as criticality studies need to compute some values of interest in neutron physics. Two kind of codes may be used : deterministic ones and stochastic ones. The stochastic codes do not require approximation and are thus more exact. However, they may require a lot of time to converge with a sufficient precision.The work carried out during this thesis aims to build an efficient acceleration strategy in the TRIPOLI-4®. We wish to implement the zero variance game. To do so, the method requires to compute the adjoint flux. The originality of this work is to directly compute the adjoint flux directly from a Monte-Carlo simulation without using external codes thanks to the fission matrix method. This adjoint flux is then used as an importance map to bias the simulation.

This study develops a dynamic importance sampling method (DIS) for numerical simulations of rare events. The DIS method is flexible, fast, and accurate. The most importance is that it is very easy to implement. It could be applied to any multifactor copula models, which conduct by arbitrary independent random variables. First, the key common factor (KCF) is determined by the maximum value among the coefficients of factor loadings. Second, searching the indicator by the order statistics and applying the truncated sampling techniques, the probability of large losses (PLL) and the expected excess loss above threshold (EELAT) can be estimated precisely. Except for the assumption that the factor loadings of KCF do not exit zero elements, we do not impose any restrictions on the composition of the portfolio. The DIS method developed in this study can therefore be applied to a very wide range of credit risk models. Comparison of the numerical experiment between the method of Glasserman, Kang and Shahabuddin (2008) and the DIS method developed in this study, under the multifactor Gaussian copula model and the high market impact condition (the factor loadings of marketwide factor of 0.8), both variance reduction ratio and efficient ratio of the DIS model are much better than that of Glasserman et al. (2008)¡¦s. And both results approximate when the factor loadings of marketwide factor decreases to the range of 0.5 to 0.25. However, the DIS method is superior to the method of Glasserman et al. (2008) in terms of the practicability. Numerical simulation results demonstrate that the DIS method is not only feasible to the general market conditions, but also particularly to the high market impact condition, especially in credit contagion or market collapse environments. It is also noted that the numerical results indicate that the DIS estimators exit bounded relative error.

Most recorded data are rounded to the nearest decimal place due to the precision of the recording mechanism. This rounding entails errors in estimation and measurement. In this paper, we compare the performances of three types of estimators based on rounded data from time series models, namely A-K corrected estimator, approximate MLE and the SOS estimator. In order to perform the comparison, the A-K corrected estimators for the MA(1) model are derived theoretically. To improve the efficiency of the estimation, two types of variance-reduction estimators are further proposed, which are based on linear combinations of aforementioned three estimators. Simulation results show the proposed variance reduction estimators significantly improve the estimation efficiency.

In this paper, we study the parameter estimation of the multiple linear time series regression model with long memory stochastic regressors and innovations. Robinson and Hidalgo (1997) and Hidalgo and Robinson (2002) proposed a class of frequency-domain weighted least squares estimates. Their estimates are shown to achieve the Gauss-Markov bound with standard convergence rate. In this study, we proposed a time-domain generalized LSE approach, in which the inverse autocovariance matrix of the innovations is estimated via autoregressive coefficients. Simulation studies are performed to compare the proposed estimates with Robinson and Hidalgo (1997) and Hidalgo and Robinson (2002). The results show the time-domain generalized LSE is comparable to Robinson and Hidalgo (1997) and Hidalgo and Robinson (2002) and attains higher efficiencies when the autoregressive or moving average coefficients of the FARIMA models have larger values. A variance reduction estimator, called TF estimator, based on linear combination of the proposed estimator and Hidalgo and Robinson (2002)'s estimator is further proposed to improve the efficiency. Bootstrap method is applied to estimate the weights of the linear combination. Simulation results show the TF estimator outperforms the frequency-domain as well as the time-domain approaches.