We consider interacting urns on a finite directed network, where both sampling and reinforcement processes depend on the nodes of the network. This extends previous research by incorporating node-dependent sampling and reinforcement. We classify the sampling and reinforcement schemes, as well as the networks on which the proportion of balls of either colour in each urn converges almost surely to a deterministic limit. We also investigate conditions for achieving synchronisation of the colour proportions across the urns and analyse fluctuations under specific conditions on the reinforcement scheme and network structure.

A Metropolis–Hastings Robbins–Monro (MH-RM) algorithm for high-dimensional maximum marginal likelihood exploratory item factor analysis is proposed. The sequence of estimates from the MH-RM algorithm converges with probability one to the maximum likelihood solution. Details on the computer implementation of this algorithm are provided. The accuracy of the proposed algorithm is demonstrated with simulations. As an illustration, the proposed algorithm is applied to explore the factor structure underlying a new quality of life scale for children. It is shown that when the dimensionality is high, MH-RM has advantages over existing methods such as numerical quadrature based EM algorithm. Extensions of the algorithm to other modeling frameworks are discussed.

Stochastic actor-oriented models (SAOMs) can be used to analyse dynamic network data, collected by observing a network and a behaviour in a panel design. The parameters of SAOMs are usually estimated by the method of moments (MoM) implemented by a stochastic approximation algorithm, where statistics defining the moment conditions correspond in a natural way to the parameters. Here, we propose to apply the generalized method of moments (GMoM), using more statistics than parameters. We concentrate on statistics depending jointly on the network and the behaviour, because of the importance of their interdependence, and propose to add contemporaneous statistics to the usual cross-lagged statistics. We describe the stochastic algorithm developed to approximate the GMoM solution. A small simulation study supports the greater statistical efficiency of the GMoM estimator compared to the MoM.

Latent variable models have been playing a central role in psychometrics and related fields. In many modern applications, the inference based on latent variable models involves one or several of the following features: (1) the presence of many latent variables, (2) the observed and latent variables being continuous, discrete, or a combination of both, (3) constraints on parameters, and (4) penalties on parameters to impose model parsimony. The estimation often involves maximizing an objective function based on a marginal likelihood/pseudo-likelihood, possibly with constraints and/or penalties on parameters. Solving this optimization problem is highly non-trivial, due to the complexities brought by the features mentioned above. Although several efficient algorithms have been proposed, there lacks a unified computational framework that takes all these features into account. In this paper, we fill the gap. Specifically, we provide a unified formulation for the optimization problem and then propose a quasi-Newton stochastic proximal algorithm. Theoretical properties of the proposed algorithms are established. The computational efficiency and robustness are shown by simulation studies under various settings for latent variable model estimation.

Alternating direction method of multipliers (ADMM) receives much attention in the field of optimization and computer science, etc. The generalized ADMM (G-ADMM) proposed by Eckstein and Bertsekas incorporates an acceleration factor and is more efficient than the original ADMM. However, G-ADMM is not applicable in some models where the objective function value (or its gradient) is computationally costly or even impossible to compute. In this paper, we consider the two-block separable convex optimization problem with linear constraints, where only noisy estimations of the gradient of the objective function are accessible. Under this setting, we propose a stochastic linearized generalized ADMM (called SLG-ADMM) where two subproblems are approximated by some linearization strategies. And in theory, we analyze the expected convergence rates and large deviation properties of SLG-ADMM. In particular, we show that the worst-case expected convergence rates of SLG-ADMM are $\mathcal{O}\left( {{N}^{-1/2}}\right)$ and $\mathcal{O}\left({\ln N} \cdot {N}^{-1}\right)$ for solving general convex and strongly convex problems, respectively, where N is the iteration number, similarly hereinafter, and with high probability, SLG-ADMM has $\mathcal{O}\left ( \ln N \cdot N^{-1/2} \right ) $ and $\mathcal{O}\left ( \left ( \ln N \right )^{2} \cdot N^{-1} \right ) $ constraint violation bounds and objective error bounds for general convex and strongly convex problems, respectively.

In this study, we consider a class of multiple-drawing opposite-reinforcing urns with time-dependent replacement rules. The class has the symmetric property of a Friedman-type urn. We divide the class into a small-increment regime and a large-increment regime. For small-increment schemes, we prove almost-sure convergence and a central limit theorem for the proportion of white balls by stochastic approximation. For large-increment schemes, by assuming the affinity condition, we show almost-sure convergence of the proportion of white balls by martingale theory and present a way to identify the limit distribution of the proportion of white balls.

In this paper we estimate the expected error of a stochastic approximation algorithm where the maximum of a function is found using finite differences of a stochastic representation of that function. An error estimate of the order $n^{-1/5}$ for the nth iteration is achieved using suitable parameters. The novelty with respect to previous studies is that we allow the stochastic representation to be discontinuous and to consist of possibly dependent random variables (satisfying a mixing condition).

The rich-get-richer rule reinforces actions that have been frequently chosen in the past. What happens to the evolution of individuals’ inclinations to choose an action when agents interact? Interaction tends to homogenize, while each individual dynamics tends to reinforce its own position. Interacting stochastic systems of reinforced processes have recently been considered in many papers, in which the asymptotic behavior is proven to exhibit almost sure synchronization. In this paper we consider models where, even if interaction among agents is present, absence of synchronization may happen because of the choice of an individual nonlinear reinforcement. We show how these systems can naturally be considered as models for coordination games or technological or opinion dynamics.

A classical Pólya urn scheme is a Markov process where the evolution is encoded by a replacement matrix (Ri, j)1 ≤ i, j ≤ d. At every discrete time-step, we draw a ball uniformly at random, denote its colour c, and replace it in the urn together with Rc, j balls of colour j (for all 1 ≤ j ≤ d). We study multiple drawing Pólya urns, where the replacement rule depends on the random drawing of a set of m balls from the urn (with or without replacement). Many particular examples of this situation have been studied in the literature, but the only general results are due to Kuba and Mahmoud (2017). These authors proved second-order asymptotic results in the two-colour case, under the so-called balance and affinity assumptions, the latter being somewhat artificial. The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to prove analogous results to Kuba and Mahmoud, but without the artificial affinity hypothesis, and, for the first time in the literature, in the d-colour case (d ≥ 3). We also provide some partial results in the two-colour nonbalanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.

We study the convergence properties of a Monte Carlo estimator proposed in the physics literature to compute the quasi-stationary distribution on a transient set of a Markov chain (see De Oliveira and Dickman (2005), (2006), and Dickman and Vidigal (2002)). Using the theory of stochastic approximations we verify the consistency of the estimator and obtain an associated central limit theorem. We provide an example showing that convergence might occur very slowly if a certain eigenvalue condition is violated. We alleviate this problem using an easy-to-implement projection step combined with averaging.

The Marcinkiewicz strong law, limn→∞(1 / n1/p)∑k=1n(Dk - D) = 0 almost surely with p ∈ (1, 2), is studied for outer products Dk = {XkX̅kT}, where {Xk} and {X̅k} are both two-sided (multivariate) linear processes (with coefficient matrices (Cl), (C̅l) and independent and identically distributed zero-mean innovations {Ξ} and {Ξ̅}). Matrix sequences Cl and C ̅l can decay slowly enough (as |l| → ∞) that {Xk,X ̅k} have long-range dependence, while {Dk} can have heavy tails. In particular, the heavy-tail and long-range-dependence phenomena for {Dk} are handled simultaneously and a new decoupling property is proved that shows the convergence rate is determined by the worst of the heavy tails or the long-range dependence, but not the combination. The main result is applied to obtain a Marcinkiewicz strong law of large numbers for stochastic approximation, nonlinear function forms, and autocovariances.

In this paper we establish the theory of weak convergence (toward a normal distribution) for both single-chain and population stochastic approximation Markov chain Monte Carlo (MCMC) algorithms (SAMCMC algorithms). Based on the theory, we give an explicit ratio of convergence rates for the population SAMCMC algorithm and the single-chain SAMCMC algorithm. Our results provide a theoretic guarantee that the population SAMCMC algorithms are asymptotically more efficient than the single-chain SAMCMC algorithms when the gain factor sequence decreases slower than O(1 / t), where t indexes the number of iterations. This is of interest for practical applications.

We study the convergence rate of randomly truncated stochastic algorithms, which consistin the truncation of the standard Robbins–Monro procedure on an increasing sequence ofcompact sets. Such a truncation is often required in practice to ensure convergence whenstandard algorithms fail because the expected-value function grows too fast. In this work,we give a self contained proof of a central limit theorem for this algorithm under localassumptions on the expected-value function, which are fairly easy to check in practice.

We consider a preferential duplication model for growing random graphs, extending previous models of duplication graphs by selecting the vertex to be duplicated with probability proportional to its degree. We show that a special case of this model can be analysed using the same stochastic approximation as for vertex-reinforced random walks, and show that ‘trapping’ behaviour can occur, such that the descendants of a particular group of initial vertices come to dominate the graph.

In various stochastic models the random equation of implicit renewal theory appears where the real random variable S and the stochastic process Ψ with index space and state space R are independent. By use of stochastic approximation the distribution function of S is recursively estimated on the basis of independent or ergodic copies of Ψ. Under integrability assumptions almost sure L1-convergence is proved. The choice of gains in the recursion is discussed. Applications are given to insurance mathematics (perpetuities) and queueing theory (stationary waiting and queueing times).

The Robbins–Monro algorithm with randomly varying truncations for measurements with non-additive noise is considered. Assuming that the function under observation is locally Lipschitz-continuous in its first argument and that the noise is a φ-mixing process, strong consistency of the estimate is shown. Neither growth rate restriction on the function, nor the decreasing rate of the mixing coefficients are required.

A stochastic gradient descent method is combined with a consistent auxiliary estimate to achieve global convergence of the recursion. Using step lengths converging to zero slower than 1/n and averaging the trajectories, yields the optimal convergence rate of 1/√n and the optimal variance of the asymptotic distribution. Possible applications can be found in maximum likelihood estimation, regression analysis, training of artificial neural networks, and stochastic optimization.

We transpose the ordinary differential equation method (used for decreasing stepsize stochastic algorithms) to a dynamical system method to study dynamical systems disturbed by a noise decreasing to zero. We prove that such an algorithm does not fall into a regular trap if the noise is exciting in an unstable direction.