Nearly optimal stochastic approximation for online principal subspace estimation

Principal component analysis(PCA) has been widely used in analyzing high-dimensional data. It converts a set of observed data points of possibly correlated variables into a set of linearly uncorrelated variables via an orthogonal transformation. To handle streaming data and reduce the complexities of PCA,(subspace)online PCA iterations were proposed to iteratively update the orthogonal transformation by taking one observed data point at a time. Existing works on the convergence of(subspace) online PCA iterations mostly focus on the case where the samples are almost surely uniformly bounded. In this paper, we analyze the convergence of a subspace online PCA iteration under more practical assumptions and obtain a nearly optimal finite-sample error bound. Our convergence rate almost matches the minimax information lower bound. We prove that the convergence is nearly global in the sense that the subspace online PCA iteration is convergent with high probability for random initial guesses. This work also leads to a simpler proof of the recent work on analyzing online PCA for the first principal component only.

Stochastic Approximation for Expensive One-Bit Feedback Systems

One-bit feedback systems generate binary data as their output and the system performance is usually measured by the success rate with a fixed parameter combination. Traditional methods need many executions for parameter optimization. Hence, it is impractical to utilize these methods in Expensive One-Bit Feedback Systems （EOBFSs）, where a single system execution is costly in terms of time or money. In this paper, we propose a novel algorithm, named Iterative Regression and Optimization （IRO）, for parameter optimization and its corresponding scheme based on the Maximum Likelihood Estimation （MLE） method and Particle Swarm Optimization （PSO） method, named MLEPSO-IRO, for parameter optimization in EOBFSs. The IRO algorithm is an iterative algorithm, with each iteration comprising two parts： regression and optimization. Considering the structure of IRO and the Bernoulli distribution property of the output of EOBFSs, MLE and a modified PSO are selected to implement the regression and optimization sections, respectively, in MLEPSO-IRO. We also provide a theoretical analysis for the convergence of MLEPSO-IRO and provide numerical experiments on hypothesized EOBFSs and one real EOBFS in comparison to traditional methods. The results indicate that MLEPSO-IRO can provide a much better result with only a small amount of system executions.

Asymptotic optimality for consensus-type stochastic approximation algorithms using iterate averaging

This paper introduces a post-iteration averaging algorithm to achieve asymptotic optimality in convergence rates of stochastic approximation algorithms for consensus control with structural constraints. The algorithm involves two stages. The first stage is a coarse approximation obtained using a sequence of large stepsizes. Then, the second stage provides a refinement by averaging the iterates from the first stage. We show that the new algorithm is asymptotically efficient and gives the optimal convergence rates in the sense of the best scaling factor and ＇smallest＇ possible asymptotic variance.

Revisiting the ODE Method for Recursive Algorithms:Fast Convergence Using Quasi Stochastic Approximation

Several decades ago,Profs.Sean Meyn and Lei Guo were postdoctoral fellows at ANU,where they shared interest in recursive algorithms.It seems fitting to celebrate Lei Guo’s 60 th birthday with a review of the ODE Method and its recent evolution,with focus on the following themes:The method has been regarded as a technique for algorithm analysis.It is argued that this viewpoint is backwards:The original stochastic approximation method was surely motivated by an ODE,and tools for analysis came much later(based on establishing robustness of Euler approximations).The paper presents a brief survey of recent research in machine learning that shows the power of algorithm design in continuous time,following by careful approximation to obtain a practical recursive algorithm.While these methods are usually presented in a stochastic setting,this is not a prerequisite.In fact,recent theory shows that rates of convergence can be dramatically accelerated by applying techniques inspired by quasi Monte-Carlo.Subject to conditions,the optimal rate of convergence can be obtained by applying the averaging technique of Polyak and Ruppert.The conditions are not universal,but theory suggests alternatives to achieve acceleration.The theory is illustrated with applications to gradient-free optimization,and policy gradient algorithms for reinforcement learning.

IMPROVED RESULTS ON THE ROBUSTNESS OF STOCHASTIC APPROXIMATION ALGORITHMS

This paper is a continuation of the research carried out in [1]-[2], where the robustnessanalysis for stochastic approximation algorithms is given for two cases: 1. The regression functionand the Liapunov function are not zero at the sought-for x~0, 2. lim supnot zero, here {ξ} are the measurement errors and {a} are the weighting coefficients in thealgorithm. Allowing these deviations from zero to occur simultaneously but to remain small, thispaper shows that the estimation error is still small even for a class fo measurement errors moregeneral than that considered in [2].

STOCHASTIC APPROXIMATION UNDER CORRELATED MEASUREMENT ERRORS

In this paper the Kiefer-Wolfowitz (KW) procedure for searching the extremum of the regression function as well as the Robbins-Monro (RM) procedure for solving the regression equation are modified in order that they can be applied to the case when the measurement errors form an ARMA process. Simple conditions are given to guarantee their convergence to the extremum and the root of regression function respectively by using a new approach combining both the probabilistic method and the ordinary differential equation (ODE) method. The results given here are better than the well-known ones even if the measurement error is the martingale difference sequence.

Asymptotic behavior of asynchronous stochastic approximation

The pathwise convergence of a distributed, asynchronous stochastic approximation (SA) scheme is analyzed. The conditions imposed on the step size and noise are the weakest in comparison with the existing ones. The step sizes in different processors are allowed to be different, and the time-delays between processors are also allowed to be different and even time-varying.

Distributed dynamic stochastic approximation algorithm over time-varying networks

In this paper,a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network.Each agent updates its estimate by using the local observation,the dynamic information of the global root,and information received from its neighbors.Compared with similar works in optimization area,we allow the observation to be noise-corrupted,and the noise condition is much weaker.Furthermore,instead of the upper bound of the estimate error,we present the asymptotic convergence result of the algorithm.The consensus and convergence of the estimates are established.Finally,the algorithm is applied to a distributed target tracking problem and the numerical example is presented to demonstrate the performance of the algorithm.

GEOMETRIC STRUCTURE IN STOCHASTIC APPROXIMATION

Let J be the zero set of the gradient fx of a function f:Rn→R. Under fairly general conditions the stochastic approximation algorithm ensures d(f(xk),f(J))→0, as k→∞. First of all, the paper considers this problem: Under what conditions the convergence d(f(xk),f(J)) → 0 implies k →∞ d(xk,J)→O. It is shown that such implication takes place if fx is continuous and f(J) is nowhere dense. Secondly, an intensified version of Sard's theorem has been proved, which itself is interesting. As a particular case, it provides two independent sufficient conditions as answers to the previous question: If f is a C1 function and either i) J is a compact set or ii) for any bounded set B, f-1(B)is bounded, then f(J) is nowhere dense. Finally, some tools in algebraic geometry are used to prove that j(J) is a finite set if f is a polynomial. Hence f(J) is nowhere dense in the polynomial case.

Stochastic level-value approximation for quadratic integer convex programming

We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.

Iterative Learning Control for Discrete-time Stochastic Systems with Quantized Information

An iterative learning control(ILC) algorithm using quantized error information is given in this paper for both linear and nonlinear discrete-time systems with stochastic noises. A logarithmic quantizer is used to guarantee an adaptive improvement in tracking performance. A decreasing learning gain is introduced into the algorithm to suppress the effects of stochastic noises and quantization errors. The input sequence is proved to converge strictly to the optimal input under the given index. Illustrative simulations are given to verify the theoretical analysis.

Joint state and parameter estimation in particle filtering and stochastic optimization

In this paper, an adaptive estimation algorithm is proposed for non-linear dynamic systems with unknown static parameters based on combination of particle filtering and Simultaneous Perturbation Stochastic Approxi- mation （SPSA） technique. The estimations of parameters are obtained by maximum-likelihood estimation and sampling within particle filtering framework, and the SPSA is used for stochastic optimization and to approximate the gradient of the cost function. The proposed algorithm achieves combined estimation of dynamic state and static parameters of nonlinear systems. Simulation result demonstrates the feasibilitv and efficiency of the proposed algorithm

Stochastic period-doubling bifurcation in biharmonic driven Duffing system with random parameter

Stochastic period-doubling bifurcation is explored in a forced Duffing system with a bounded random parameter as an additional weak harmonic perturbation added to the system. Firstly, the biharmonic driven Duffing system with a random parameter is reduced to its equivalent deterministic one, and then the responses of the stochastic system can be obtained by available effective numerical methods. Finally, numerical simulations show that the phase of the additional weak harmonic perturbation has great influence on the stochastic period-doubling bifurcation in the biharmonic driven Duffing system. It is emphasized that, different from the deterministic biharmonic driven Duffing system, the intensity of random parameter in the Duffing system can also be taken as a bifurcation parameter, which can lead to the stochastic period-doubling bifurcations.

An Improved SPSA Algorithm for System Identification Using Fuzzy Rules for Training Neural Networks

Simultaneous perturbation stochastic approximation （SPSA） belongs to the class of gradient-free optimization methods that extract gradient information from successive objective function evaluation. This paper describes an improved SPSA algorithm, which entails fuzzy adaptive gain sequences, gradient smoothing, and a step rejection procedure to enhance convergence and stability. The proposed fuzzy adaptive simultaneous perturbation approximation （FASPA） algorithm is particularly well suited to problems involving a large number of parameters such as those encountered in nonlinear system identification using neural networks （NNs）. Accordingly, a multilayer perceptron （MLP） network with popular training algorithms was used to predicate the system response. We found that an MLP trained by FASPSA had the desired accuracy that was comparable to results obtained by traditional system identification algorithms. Simulation results for typical nonlinear systems demonstrate that the proposed NN architecture trained with FASPSA yields improved system identification as measured by reduced time of convergence and a smaller identification error.

RECURSIVE SYSTEM IDENTIFICATION

Most of existing methods in system identification with possible exception of those for linear systems are off-line in nature, and hence are nonrecursive. This paper demonstrates the recent progress in recursive system identification. The recursive identification algorithms are presented not only for linear systems （multivariate ARMAX systems） but also for nonlinear systems such as the Hammerstein and Wiener systems, and the nonlinear ARX systems. The estimates generated by the algorithms are online updated and converge a.s. to the true values as time tends to infinity.

Recursive estimation algorithms for power controls of wireless communication networks

Power control problems for wireless communication networks are investigated in direct-sequence codedivision multiple-access （DS/CDMA） channels. It is shown that the underlying problem can be formulated as a constrained optimization problem in a stochastic framework. For effective solutions to this optimization problem in real time, recursive algorithms of stochastic approximation type are developed that can solve the problem with unknown system components. Under broad conditions, convergence of the algorithms is established by using weak convergence methods.

Construction and Update of an Online Ensemble Score Involving Linear Discriminant Analysis and Logistic Regression

The present aim is to update, upon arrival of new learning data, the parameters of a score constructed with an ensemble method involving linear discriminant analysis and logistic regression in an online setting, without the need to store all of the previously obtained data. Poisson bootstrap and stochastic approximation processes were used with online standardized data to avoid numerical explosions, the convergence of which has been established theoretically. This empirical convergence of online ensemble scores to a reference “batch” score was studied on five different datasets from which data streams were simulated, comparing six different processes to construct the online scores. For each score, 50 replications using a total of 10N observations (N being the size of the dataset) were performed to assess the convergence and the stability of the method, computing the mean and standard deviation of a convergence criterion. A complementary study using 100N observations was also performed. All tested processes on all datasets converged after N iterations, except for one process on one dataset. The best processes were averaged processes using online standardized data and a piecewise constant step-size.

A STOCHASTIC NEWTON METHOD FOR NONLINEAR EQUATIONS

In this paper,we study a stochastic Newton method for nonlinear equations,whose exact function information is difficult to obtain while only stochastic approximations are available.At each iteration of the proposed algorithm,an inexact Newton step is first computed based on stochastic zeroth-and first-order oracles.To encourage the possible reduction of the optimality error,we then take the unit step size if it is acceptable by an inexact Armijo line search condition.Otherwise,a small step size will be taken to help induce desired good properties.Then we investigate convergence properties of the proposed algorithm and obtain the almost sure global convergence under certain conditions.We also explore the computational complexities to find an approximate solution in terms of calls to stochastic zeroth-and first-order oracles,when the proposed algorithm returns a randomly chosen output.Furthermore,we analyze the local convergence properties of the algorithm and establish the local convergence rate in high probability.At last we present preliminary numerical tests and the results demonstrate the promising performances of the proposed algorithm.

A Simple Model for On-Sensor Phase-Detection Autofocusing Algorithm

A simple model of the phase-detection autofocus device based on the partially masked sensor pixels is described. The cross-correlation function of the half-images registered by the masked pixels is proposed as a focus function. It is shown that—in such setting—focusing is equivalent to searching of the cross-correlation function maximum. Application of stochastic approximation algorithms to unimodal and non-unimodal focus functions is shortly discussed.

A Symmetric Linearized Alternating Direction Method of Multipliers for a Class of Stochastic Optimization Problems

Alternating direction method of multipliers(ADMM)receives much attention in the recent years due to various demands from machine learning and big data related optimization.In 2013,Ouyang et al.extend the ADMM to the stochastic setting for solving some stochastic optimization problems,inspired by the structural risk minimization principle.In this paper,we consider a stochastic variant of symmetric ADMM,named symmetric stochastic linearized ADMM(SSL-ADMM).In particular,using the framework of variational inequality,we analyze the convergence properties of SSL-ADMM.Moreover,we show that,with high probability,SSL-ADMM has O((ln N)·N^(-1/2))constraint violation bound and objective error bound for convex problems,and has O((ln N)^(2)·N^(-1))constraint violation bound and objective error bound for strongly convex problems,where N is the iteration number.Symmetric ADMM can improve the algorithmic performance compared to classical ADMM,numerical experiments for statistical machine learning show that such an improvement is also present in the stochastic setting.