Stochastic approximation has been widely used since first proposed by Herbert Robbins and Sutton Monro in 1951. It is an iterative stochastic method that attempts to find the zeros of functions that cannot be computed directly. In this thesis, we used the technique in several different aspects. It was used in the analysis of large geostatistical data, in the improvement of simulated annealing algorithm also, as well as for NMR protein structure determination. 1. We proposed a resampling based Stochastic approximation method for the analysis of large geostatistical data. The main difficulty that lies in the analysis of geostatistical data is the computation time is extremely long when the sample size becomes large. Our proposed method only use a small portion of the data at each iteration. Each time, we update our estimators based on a randomly selected subset of the data using stochastic approximation. In this way, we use the information from the whole data set while keep the computation time almost irrelevant to the sample size. We proved the consistency of our estimator and showed by simulation study that the computation time is much reduced compared to other existing methods. 2. Simulated Annealing algorithm has been widely used for optimization problems. However, it can not guarantee the global optima to be located unless a logarithmic cooling schedule is used. However, the logarithm rate is so slow that no one can afford such a long cpu time. We proposed a new stochastic optimization algorithm, the so-called simulated stochastic approximation annealing (SAA) algorithm, which is a combination of simulated annealing and the stochastic approximation Monte Carlo (SAMC) algorithm. It is shown that the new algorithm can work with a cooling schedule that decreases much faster than in the logarithmic cooling schedule while guarantee the global optima to be reached when temperature tends to zero. 3. Protein Structure determination is a very important topic in computational biology. It aims to determine different conformations for each protein, which helps to understand biological functions such as protein-protein interactions, protein-DNA interactions and so on. Protein structure determination consists of a series of steps and peak picking is a very important step. It is the prerequisite for all other steps. Manually pick the peaks is very time consuming. To automate this process, several methods have been proposed. However, due to the complexity of NMR spectra, the existing method is hard to distinguish false peaks and true peaks perfectly. The main difficulty lies in identifying true peaks with low intensity and overlapping peaks. We propose to model the spectrum as a mixture of bivariate Gaussian densities and used stochastic approximation Monte Carlo (SAMC) method as the computational approach to solve this problem. Essentially, by putting the peak picking problem into a Bayesian framework, we turned it into a model selection problem. Because Bayesian method will automatically penalize including too much component into the model, our model will distinguish true peaks from noises without pre-process of the data.

The problem of robotic mapping, also known as simultaneous localization and mapping (SLAM), by a mobile agent for large distributed environments is addressed in this dissertation. This has sometimes been referred to as the holy grail in the robotics community, and is the stepping stone towards making a robot completely autonomous. A hybrid solution to the SLAM problem is proposed based on "first localize then map" principle. It is provably consistent and has great potential for real time application. It provides significant improvements over state-of-the-art Bayesian approaches by reducing the computational complexity of the SLAM problem without sacrificing consistency. The localization is achieved using a feature based extended Kalman filter (EKF) which utilizes a sparse set of reliable features. The common issues of data association, loop closure and computational cost of EKF based methods are kept tractable owing to the sparsity of the feature set. A novel frequentist mapping technique is proposed for estimating the dense part of the environment using the sensor observations. Given the pose estimate of the robot, this technique can consistently map the surrounding environment. The technique has linear time complexity in map components and for the case of bounded sensor noise, it is shown that the frequentist mapping technique has constant time complexity which makes it capable of estimating large distributed environments in real time. The frequentist mapping technique is a stochastic approximation algorithm and is shown to converge to the true map probabilities almost surely. The Hybrid SLAM software is developed in the C-language and is capable of handling real experimental data as well as simulations. The Hybrid SLAM technique is shown to perform well in simulations, experiments with an iRobot Create, and on standard datasets from the Robotics Data Set Repository, known as Radish. It is demonstrated that the Hybrid SLAM technique can successfully map large complex data sets in an order of magnitude less time than the time taken by the robot to acquire the data. It has low system requirements and has the potential to run on-board a robot to estimate large distributed environments in real time.

Graduation date: 1995

<p> In this thesis a non-parametric normalized stochastic approximation algorithm has been developed for the identification of multivariable systems from noisy data without prior knowledge of the statistics of measurement noise.</p> <p> The system model is first transformed into a special canonical form, then it is formulated in a non-parametric form. The parameters of this model are estimated through a normalized stochastic approximation algorithm. Finally, the system parameters are recovered from these estimates by another transformation.</p> <p> The proposed algorithm is applied to the identification of two simulated systems.</p> <p> Conclusions of this work and suggestions for future work are given.</p> / Thesis / Master of Engineering (MEngr)

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(lambda) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(lambda) and Q-learning belong.

Thesis (Ph. D.)--University of Texas at Austin, 2001. / Vita. Includes bibliographical references. Available also from UMI/Dissertation Abstracts International.

Thesis (Ph. D.)--Rutgers University, 2009. / "Graduate Program in Statistics." Includes bibliographical references (p. 83-87).

Not available / text

Thesis (Ph. D.)--Carleton University, 1995. / Also available in electronic format on the Internet.

Optimization problems involving uncertainties are common in a variety of engineering disciplines such as transportation systems, manufacturing, communication networks, healthcare and finance. The large number of input variables and the lack of a system model prohibit a precise analytical solution and a viable alternative is to employ simulation-based optimization. The idea here is to simulate a few times the stochastic system under consideration while updating the system parameters until a good enough solution is obtained. Formally, given only noise-corrupted measurements of an objective function, we wish to end a parameter which minimises the objective function. Iterative algorithms using statistical methods search the feasible region to improve upon the candidate parameter. Stochastic approximation algorithms are best suited; most studied and applied algorithms for funding solutions when the feasible region is a continuously valued set. One can use information on the gradient/Hessian of the objective to aid the search process. However, due to lack of knowledge of the noise distribution, one needs to estimate the gradient/Hessian from noisy samples of the cost function obtained from simulation. Simple gradient search schemes take much iteration to converge to a local minimum and are heavily dependent on the choice of step-sizes. Stochastic Newton methods, on the other hand, can counter the ill-conditioning of the objective function as they incorporate second-order information into the stochastic updates. Stochastic Newton methods are often more accurate than simple gradient search schemes. We propose enhancements to the Hessian estimation scheme used in two recently proposed stochastic Newton methods, based on the ideas of random directions stochastic approximation (2RDSA) [21] and simultaneous perturbation stochastic approximation (2SPSA-31) [6], respectively. The proposed scheme, inspired by [29], reduces the error in the Hessian estimate by (i) Incorporating a zero-mean feedback term; and (ii) optimizing the step-sizes used in the Hessian recursion. We prove that both 2RDSA and 2SPSA-3 with our Hessian improvement scheme converges asymptotically to the true Hessian. The key advantage with 2RDSA and 2SPSA-3 is that they require only 75% of the simulation cost per-iteration for 2SPSA with improved Hessian estimation (2SPSA-IH) [29]. Numerical experiments show that 2RDSA-IH outperforms both 2SPSA-IH and 2RDSA without the improved Hessian estimation scheme.