Generalization bounds of ERM algorithm with Markov chain samples

One of the main goals of machine learning is to study the generalization performance of learning algorithms. The previous main results describing the generalization ability of learning algorithms are usually based on independent and identically distributed （i.i.d.） samples. However, independence is a very restrictive concept for both theory and real-world applications. In this paper we go far beyond this classical framework by establishing the bounds on the rate of relative uniform convergence for the Empirical Risk Minimization （ERM） algorithm with uniformly ergodic Markov chain samples. We not only obtain generalization bounds of ERM algorithm, but also show that the ERM algorithm with uniformly ergodic Markov chain 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.     

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.     

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.     

基于$\alpha$\,-混合序列的学习机器一致收敛速率的界

Vapnik, Cucker和Smale已经证明了, 当样本的数目趋于无限时, 基于独立同分布序列学习机器的经验 风险会一致收敛到它的期望风险\bd 本文把这些基于独立同分布序列的结果推广到了$\alpha$\,-混合序列, 应用Markov不等式得到了基于$\alpha$\,-混合序列的学习机器一致收敛速率的界     

基于α-混合序列的学习机器一致收敛速率的界

Vapnik,Cucker和Smale已经证明了,当样本的数目趋于无限时,基于独立同分布序列学习机器的经验风险会一致收敛到它的期望风险.本文把这些基于独立同分布序列的结果推广到了α-混合序列,应用Markov不等式得到了基于α-混合序列的学习机器一致收敛速率的界.     

Convergence of Online Gradient Method with Penalty for BP Neural Networks

Online gradient method has been widely used as a learning algorithm for training feedforward neural networks. Penalty is often introduced into the training procedure to improve the generalization performance and to decrease the magnitude of network weights. In this paper, some weight boundedness and deterministic con- vergence theorems are proved for the online gradient method with penalty for BP neural network with a hidden layer, assuming that the training samples are supplied with the network in a fixed order within each epoch. The monotonicity of the error function with penalty is also guaranteed in the training iteration. Simulation results for a 3-bits parity problem are presented to support our theoretical results.     

基于代数等价路径的一致P-函数非线性互补问题的可行内点算法

对一致P-函数非线性互补问题，提出了一种新的基于代数等价路径的可行内点算法，并讨论了计算复杂性．该算法可以在任一内部可行点启动，并且全局收敛；当初始点靠近中心路径时，此算法便成为中心路径跟踪算法，特别对于单调线性互补问题，总迭代次数为O（√nL），其中L是问题的输入长度。     

Learning from regularized regression algorithms with <Emphasis Type="Italic">p</Emphasis>-order Markov chain sampling

Evaluation for the performance of learning algorithm has been the main thread of theoretical research of machine learning. The performance of the regularized regression algorithm based on independent and identically distributed(i.i.d.) samples has been researched by a large number of references. In the present paper we provide the convergence rates for the performance of regularized regression based on the inputs of p-order Markov chains.     

Constrained LQR problems in elliptic distributed control systems with point observations—convergence results

In this paper constrained LQR problems in distributed control systems governed by the elliptic equation with point observations are studied. A variational inequality approach coupled with potential theory in a Banach space setting is adopted. First the admissible control set is extended to be bounded by two functions, and feedback characterization of the optimal control in terms of the optimal state is derived; then two numerical algorithms proposed in [5] are modified, and the strong convergence and uniform convergence in Banach space are proved. This verifies that the numerical algorithm is insensitive to the partition number of the boundary. Since our control variables are truncated below and above by two functions inL ^p and in our numerical computation only the layer density not the control variable is assumed to be piecewise smooth, uniform convergence guarantees a better convergence. Finally numerical computation for an example is carried out and confirms the analysis. This research was supported in part by NSF Grant DMS-9404380 and by an IRI Award of Texas A&M University. The current address of the first author is the Department of Mathematical Science, University of Nevada at Las Vegas, Las Vegas, NV 89154, USA.     

Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

Solutions of learning problems by Empirical Risk Minimization (ERM) – and almost-ERM when the minimizer does not exist – need to be consistent, so that they may be predictive. They also need to be well-posed in the sense of being stable, so that they might be used robustly. We propose a statistical form of stability, defined as leave-one-out (LOO) stability. We prove that for bounded loss classes LOO stability is (a) sufficient for generalization, that is convergence in probability of the empirical error to the expected error, for any algorithm satisfying it and, (b) necessary and sufficient for consistency of ERM. Thus LOO stability is a weak form of stability that represents a sufficient condition for generalization for symmetric learning algorithms while subsuming the classical conditions for consistency of ERM. In particular, we conclude that a certain form of well-posedness and consistency are equivalent for ERM. Dedicated to Charles A. Micchelli on his 60th birthday Mathematics subject classifications (2000) 68T05, 68T10, 68Q32, 62M20. Tomaso Poggio: Corresponding author.     

基于模糊粗糙样本的统计学习理论的理论基础

介绍模糊粗糙理论的基本内容;提出模糊粗糙经验风险泛函,模糊粗糙期望风险泛函,模糊粗糙经验风险最小化原则等概念;最后证明基于模糊粗糙样本的统计学习理论的关键定理并构建学习过程一致收敛速度的界.     

Convergence of over-relaxed contraction-proximal point algorithm in Hilbert spaces

The proximal point algorithm (PPA) is a classical method for finding zeros of maximal monotone operators. It is known that the algorithm only has weak convergence in a general Hilbert space. Recently, Wang, Wang and Xu proposed two modifications of the PPA and established strong convergence theorems on these two algorithms. However, these two convergence theorems exclude an important case, namely, the over-relaxed case. In this paper, we extend the above convergence theorems from under-relaxed case to the over-relaxed case, which in turn improve the performance of these two algorithms. Preliminary numerical experiments show that the algorithm with over-relaxed parameter performs better than that with under-relaxed parameter.     

Generalization errors of Laplacian regularized least squares regression

Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced.     

A Mehrotra-type predictor-corrector algorithm with polynomiality andQ-subquadratic convergence

Mehrotra's predictor-corrector algorithm [3] is currently considered to be one of the most practically efficient interior-point methods for linear programming. Recently, Zhang and Zhang [18] studied the global convergence properties of the Mehrotra-type predictor-corrector approach and established polynomial complexity bounds for two interior-point algorithms that use the Mehrotra predictor-corrector approach. In this paper, we study the asymptotic convergence rate for the Mehrotra-type predictor-corrector interior-point algorithms. In particular, we construct an infeasible-interior-point algorithm based on the second algorithm proposed in [18] and show that while retaining a complexity bound ofO(n ^1.5 t)-iterations, under certain conditions the algorithm also possesses aQ-subquadratic convergence, i.e., a convergence ofQ-order 2 with an unboundedQ-factor.Research supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171.     

若干基于模糊随机样本的SLT定理

基于模糊随机样本空间,提出了模糊随机期望风险泛函,模糊随机经验风险泛函和模糊随机经验风险泛函最小化原则等概念;基于模糊随机变量及其期望,讨论了相关概率不等式;最后证明了基于模糊随机样本统计学习理论的关键定理并研究了学习过程一致收敛速度的界等问题.     

Aggregated estimators and empirical complexity for least square regression

Numerous empirical results have shown that combining regression procedures can be a very efficient method. This work provides PAC bounds for the L² generalization error of such methods. The interest of these bounds are twofold.First, it gives for any aggregating procedure a bound for the expected risk depending on the empirical risk and the empirical complexity measured by the Kullback–Leibler divergence between the aggregating distribution and a prior distribution π and by the empirical mean of the variance of the regression functions under the probability .Secondly, by structural risk minimization, we derive an aggregating procedure which takes advantage of the unknown properties of the best mixture : when the best convex combination of d regression functions belongs to the d initial functions (i.e. when combining does not make the bias decrease), the convergence rate is of order (logd)/N. In the worst case, our combining procedure achieves a convergence rate of order which is known to be optimal in a uniform sense when (see [A. Nemirovski, in: Probability Summer School, Saint Flour, 1998; Y. Yang, Aggregating regression procedures for a better performance, 2001]).As in AdaBoost, our aggregating distribution tends to favor functions which disagree with the mixture on mispredicted points. Our algorithm is tested on artificial classification data (which have been also used for testing other boosting methods, such as AdaBoost).     

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.