Learning from uniformly ergodic Markov chains

Evaluation for generalization performance of learning algorithms has been the main thread of machine learning theoretical research. The previous bounds describing the generalization performance of the empirical risk minimization (ERM) algorithm are usually established based on independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by establishing the generalization bounds of the ERM algorithm with uniformly ergodic Markov chain (u.e.M.c.) samples. We prove the bounds on the rate of uniform convergence/relative uniform convergence of the ERM algorithm with u.e.M.c. samples, and show that the ERM algorithm with u.e.M.c. samples is consistent. The established theory underlies application of ERM type of learning algorithms.     

Generalization bounds of ERM algorithm with V-geometrically Ergodic Markov chains

The previous results describing the generalization ability of Empirical Risk Minimization (ERM) algorithm are usually based on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by establishing the first exponential bound on the rate of uniform convergence of the ERM algorithm with V-geometrically ergodic Markov chain samples, as the application of the bound on the rate of uniform convergence, we also obtain the generalization bounds of the ERM algorithm with V-geometrically ergodic Markov chain samples and prove that the ERM algorithm with V-geometrically ergodic Markov chain samples is consistent. The main results obtained in this paper extend the previously known results of i.i.d. observations to the case of V-geometrically ergodic Markov chain samples.     

Generalization performance of least-square regularized regression algorithm with Markov chain samples

The previously known works describing the generalization of least-square regularized regression algorithm are usually based on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by studying the generalization of least-square regularized regression algorithm with Markov chain samples. We first establish a novel concentration inequality for uniformly ergodic Markov chains, then we establish the bounds on the generalization of least-square regularized regression algorithm with uniformly ergodic Markov chain samples, and show that least-square regularized regression algorithm with uniformly ergodic Markov chains is consistent.     

New Bernstein's Inequalities for Dependent Observations and Applications to Learning Theory

The classical concentration inequalities deal with the deviations of functions of independent and identically distributed (i.i.d.) random variables from their expectation and these inequalities have numerous important applications in statistics and machine learning theory. In this paper we go far beyond this classical framework by establish two new Bernstein type concentration inequalities for -mixing sequence and uniformly ergodic Markov chains. As the applications of the Bernstein's inequalities, we also obtain the bounds on the rate of uniform deviations of empirical risk minimization (ERM) algorithms based on -mixing observations.     

Ergodic backward stochastic difference equations

We consider ergodic backward stochastic differential equations in a discrete time setting, where noise is generated by a finite state Markov chain. We show existence and uniqueness of solutions, along with a comparison theorem. To obtain this result, we use a Nummelin splitting argument to obtain ergodicity estimates for a discrete time Markov chain which hold uniformly under suitable perturbations of its transition matrix. We conclude with an application of this theory to a treatment of an ergodic control problem.     

Perturbation bounds for Monte Carlo within Metropolis via restricted approximations

The Monte Carlo within Metropolis (MCwM) algorithm, interpreted as a perturbed Metropolis–Hastings (MH) algorithm, provides an approach for approximate sampling when the target distribution is intractable. Assuming the unperturbed Markov chain is geometrically ergodic, we show explicit estimates of the difference between the $n$th step distributions of the perturbed MCwM and the unperturbed MH chains. These bounds are based on novel perturbation results for Markov chains which are of interest beyond the MCwM setting. To apply the bounds, we need to control the difference between the transition probabilities of the two chains and to verify stability of the perturbed chain.     

Uniform ergodicities and perturbation bounds of Markov chains on base norm spaces

It is known that Dobrushin's ergodicity coefficient is one of the effective tools in the investigations of limiting behavior of Markov processes. Several interesting properties of the ergodicity coefficient of a positive mapping defined on base norm spaces have been studied. In this paper, we consider uniformly mean ergodic and asymptotically stable Markov operators on such spaces. In terms of the ergodicity coefficient, we establish uniform mean ergodicity criterion. Moreover, we develop the perturbation theory for uniformly asymptotically stable Markov chains on base norm spaces. In particularly, main results open new perspectives in the perturbation theory for quantum Markov processes defined on von Neumann algebras.     

Geometric ergodicity for classes of homogeneous Markov chains

The paper deals with non asymptotic computable bounds for the geometric convergence rate of homogeneous ergodic Markov processes. Some sufficient conditions are stated for simultaneous geometric ergodicity of Markov chain classes. This property is applied to nonparametric estimation in ergodic diffusion processes.     

Fast perfect sampling from linear extensions

In this paper, we study the problem of sampling (exactly) uniformly from the set of linear extensions of an arbitrary partial order. Previous Markov chain techniques have yielded algorithms that generate approximately uniform samples. Here, we create a bounding chain for one such Markov chain, and by using a non-Markovian coupling together with a modified form of coupling from the past, we build an algorithm for perfectly generating samples. The expected running time of the procedure is O(n³lnn), making the technique as fast as the mixing time of the Karzanov/Khachiyan chain upon which it is based.     

Error bounds for augmented truncation approximations of continuous-time Markov chains

This paper considers the augmented truncation approximation of the generator of an ergodic continuous-time Markov chain with a countably infinite state space. The main purpose of this paper is to present bounds for the absolute difference between the stationary distributions of the original generator and its augmented truncation. As examples, we apply the bounds to an $M∕M∕s$ retrial queue and an upper Hessenberg Markov chain.     

Random walk centrality and a partition of Kemeny’s constant

We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny’s constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state in question, and two in terms of the transition matrix associated with the Markov chain. Several bounds are provided on the accessibility index in terms of the eigenvalues of the transition matrix and the stationary vector, and the bounds are shown to be tight. The behaviour of the accessibility index under perturbation of the transition matrix is investigated, and examples exhibiting some counter-intuitive behaviour are presented. Finally, we characterize the situation in which the accessibility indices for all states coincide.     

Sample path optimality for a Markov optimization problem

We study a unichain Markov decision process i.e. a controlled Markov process whose state process under a stationary policy is an ergodic Markov chain. Here the state and action spaces are assumed to be either finite or countable. When the state process is uniformly ergodic and the immediate cost is bounded then a policy that minimizes the long-term expected average cost also has an nth stage sample path cost that with probability one is asymptotically less than the nth stage sample path cost under any other non-optimal stationary policy with a larger expected average cost. This is a strengthening in the Markov model case of the a.s. asymptotically optimal property frequently discussed in the literature.     

New approaches to statistical learning theory

We present new tools from probability theory that can be applied to the analysis of learning algorithms. These tools allow to derive new bounds on the generalization performance of learning algorithms and to propose alternative measures of the complexity of the learning task, which in turn can be used to derive new learning algorithms.     

The Central Limit Theorem for Markov Chains with General State Space

We consider a Markov chain with general state space and an embedded Markov chain sampled at the times of successive returns to a subsetA₀ of the state space.We assume that the latter chain is uniformly ergodic but the originalMarkov chain need not possess this property.We develop amodification of the spectralmethod and utilize it in proving the central limit theorem for theMarkov chain under consideration.     

Generalization performance of graph-based semi-supervised classification

Semi-supervised learning has been of growing interest over the past few years and many methods have been proposed. Although various algorithms are provided to implement semi-supervised learning,there are still gaps in our understanding of the dependence of generalization error on the numbers of labeled and unlabeled data. In this paper,we consider a graph-based semi-supervised classification algorithm and establish its generalization error bounds. Our results show the close relations between the generalizat...     

Quantitative Non-Geometric Convergence Bounds for Independence Samplers

We provide precise, rigorous, fairly sharp quantitative upper and lower bounds on the time to convergence of independence sampler MCMC algorithms which are not geometrically ergodic. This complements previous work on the geometrically ergodic case. Our results illustrate that even simple-seeming Markov chains often converge extremely slowly, and furthermore slight changes to a parameter value can have an enormous effect on convergence times.     

CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

1 IntroductionOne of tlle fundamental issues about the theory of evolutionary algorithIns is their conver-gence. At present, the theoretical basis about evolutionary computation is still yery wcak['--'],especial1y for the researches into the convergeIlce rates of evolutionary a1gorithm8. Accord-illg to the literature, tllere are few results about the convergence rates[4--9], but this research..area i8 very importallt in both theory and practice. Xu and Li[l0] pointed out that the studyof the…     

渐近循环马氏链的收敛速度

引入了渐近循环马氏链的概念,它是循环马氏链概念的推广.首先研究了在强遍历的条件下,可列循环马氏链的收敛速度,作为主要结论给出了当满足不同条件时可列渐近循环马氏链的C-强遍历性,一致C-强遍历性和一致C-强遍历的收敛速度     

Central limit theorem for nonhomogeneous processes with independent increments with semi-Markov switchings

The central limit theorem for nonhomogeneous processes with independent increments with semi-Markov switchings with a uniformly ergodic imbedded Markov chain is proved.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 1, pp. 134–137, January, 1991.     

Geometry of interpolation sets in derivative free optimization

We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algorithm is to maintain an interpolation sampling set so that this constant remains small, and at least uniformly bounded. This constant is often described through the basis of Lagrange polynomials associated with the interpolation set. We provide an alternative, more intuitive, definition for this concept and show how this constant is related to the condition number of a certain matrix. This relation enables us to provide a range of algorithms whilst maintaining the interpolation set so that this condition number or the geometry constant remain uniformly bounded. We also derive bounds on the error between the model and the function and between their derivatives, directly in terms of this condition number and of this geometry constant.