An analysis of convergence for a learning version of the subspace method

The learning subspace method of pattern recognition has been earlier introduced by Kohonen et al. in a speech recognition application, where the phonemes to be classified are given as spectral representations. In that method, the class subspaces are updated recursively using special rotation matrices, which depend on the training vectors entering one at a time. Here the learning algorithm based on these operators is represented in a general mathematical form, and almost sure convergence is shown to a given criterion that is a function of the statistics of the training set as well as of a set of nonrandom but free parameters. The proof employs current techniques in stochastic approximation theory. For illustration, the resulting classification criterion is then applied to a concrete pattern recognition situation with suitably chosen parameter values.     

An implicit Euler scheme with non-uniform time discretization for heat equations with multiplicative noise

We present an algorithm for solving stochastic heat equations, whose key ingredient is a non-uniform time discretization of the driving Brownian motion W. For this algorithm we derive an error bound in terms of its number of evaluations of one-dimensional components of W. The rate of convergence depends on the spatial dimension of the heat equation and on the decay of the eigenfunctions of the covariance of W. According to known lower bounds, our algorithm is optimal, up to a constant, and this optimality cannot be achieved by uniform time discretizations. AMS subject classification (2000)  60H15, 60H35, 65C30     

Heuristic and optimization approaches to extending the Kohonen self organizing algorithm

The Kohonen self organizing neural network has been applied to an increasingly wider range of application problems that traditionally have been the domain of statistical and operational research techniques, such as data clustering and classification, and optimization and control. This Kohonen network is bestowed with a number of unique strengths which are, unfortunately, matched by an equally formidable set of limitations due its learning algorithm. There have been extensive studies over the last decade to extend the Kohonen neural network using heuristic and optimization approaches. This paper provides a comprehensive survey of the research efforts directed to enhancing the Kohonen self organizing neural network and its learning algorithm. We also point out some research directions for pursuing further improvements.     

Meta-control of an interacting-particle algorithm for global optimization

A common issue for stochastic global optimization algorithms is how to set the parameters of the sampling distribution (e.g. temperature, mutation/cross-over rates, selection rate, etc.) so that the samplings converge to the optimum effectively and efficiently. We consider an interacting-particle algorithm and develop a meta-control methodology which analytically guides the inverse temperature parameter of the algorithm to achieve desired performance characteristics (e.g. quality of the final outcome, algorithm running time, etc.). The main aspect of our meta-control methodology is to formulate an optimal control problem where the fractional change in the inverse temperature parameter is the control variable. The objectives of the optimal control problem are set according to the desired behavior of the interacting-particle algorithm. The control problem considers particles’ average behavior, rather than treating the behavior of individual particles. The solution to the control problem provides feedback on the inverse temperature parameter of the algorithm.     

Robin型离散Schwarz波形松弛算法的收敛性分析

Schwarz波形松弛(Schwarz waveform relaxation,SWR)是一种新型区域分解算法,是当今并行计算研究领域的焦点之一,但针对该算法的收敛性分析基本上都停留在时空连续层面.从实际计算角度看,分析离散SWR算法的收敛性更重要.本文考虑SWR研究领域中非常流行的Robin型人工边界条件,分析时空离散参数t和x、模型参数等因素对算法收敛速度的影响.Robin型人工边界条件中含有一个自由参数p,可以用来优化算法的收敛速度,但最优参数的选取却需要求解一个非常复杂的极小-极大问题.本文对该极小-极大问题进行深入分析,给出最优参数的计算方法.本文给出的数值实验结果表明所获最优参数具有以下优点:(1)相比连续情形下所获最优参数,利用离散情形下获得的参数可以进一步提高Robin型SWR算法在实际计算中的收敛速度,当固定t或x而令另一个趋于零时,利用离散情形下所获参数可以使算法的收敛速度具有鲁棒性(即收敛速度不随离散参数的减小而持续变慢).(2)相比连续情形下所获收敛速度估计,离散情形下获得的收敛速度估计可以更加准确地预测算法的实际收敛速度.     

Analysis of Support Vector Machines Regression

Support vector machines regression (SVMR) is a regularized learning algorithm in reproducing kernel Hilbert spaces with a loss function called the ε-insensitive loss function. Compared with the well-understood least square regression, the study of SVMR is not satisfactory, especially the quantitative estimates of the convergence of this algorithm. This paper provides an error analysis for SVMR, and introduces some recently developed methods for analysis of classification algorithms such as the projection operator and the iteration technique. The main result is an explicit learning rate for the SVMR algorithm under some assumptions. Research supported by NNSF of China No. 10471002, No. 10571010 and RFDP of China No. 20060001010.     

基于简单二次函数模型的带线搜索的信赖域算法

基于简单二次函数模型, 结合非精确大步长Armijo线搜索技术, 建立了一个新的求解无约束最优化问题的组合信赖域与线搜索算法, 证明了算法的全局收敛性. 数值例子表明算法是有效的, 适合求解大规模问题.       

Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.     

A smoothing algorithm for finite min–max–min problems

We generalize a smoothing algorithm for finite min–max to finite min–max–min problems. We apply a smoothing technique twice, once to eliminate the inner min operator and once to eliminate the max operator. In mini–max problems, where only the max operator is eliminated, the approximation function is decreasing with respect to the smoothing parameter. Such a property is convenient to establish algorithm convergence, but it does not hold when both operators are eliminated. To maintain the desired property, an additional term is added to the approximation. We establish convergence of a steepest descent algorithm and provide a numerical example.     

Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery

The matrix rank minimization problem arises in many engineering applications. As this problem is NP-hard, a nonconvex relaxation of matrix rank minimization, called the Schatten-p quasi-norm minimization(0 p 1), has been developed to approximate the rank function closely. We study the performance of projected gradient descent algorithm for solving the Schatten-p quasi-norm minimization(0 p 1) problem.Based on the matrix restricted isometry property(M-RIP), we give the convergence guarantee and error bound for this algorithm and show that the algorithm is robust to noise with an exponential convergence rate.     

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition, if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can be false when the perturbation parameter goes to zero quadratically.      

Bifurcations of fuzzy nonlinear dynamical systems

We present some recent developments of the fuzzy generalized cell mapping method (FGCM) in this paper. The topological property of the FGCM and its finite convergence of membership distribution vector are discussed. Powerful algorithms of digraphs are adopted for the analysis of topological properties of the FGCM systems. Bifurcations of fuzzy nonlinear dynamical systems are studied by using the FGCM method. A backward algorithm is introduced to study the unstable equilibrium solutions and their bifurcation. We have found that near the deterministic bifurcation point, the fuzzy system undergoes a complex transition as the control parameter varies. In this transition region, the steady state membership distribution is dependent on the initial condition. If we use the measure and topology of the α-cut (α = 1) of the steady state membership function of the persistent group representing the stable fuzzy equilibrium solution to characterize the fuzzy bifurcation, assuming the uniform initial condition within the persistent group, the bifurcation of the fuzzy dynamical system is then completed within an interval of the control parameter, rather than at a point as is the case of deterministic systems.     

Gradient learning in a classification setting by gradient descent

Learning gradients is one approach for variable selection and feature covariation estimation when dealing with large data of many variables or coordinates. In a classification setting involving a convex loss function, a possible algorithm for gradient learning is implemented by solving convex quadratic programming optimization problems induced by regularization schemes in reproducing kernel Hilbert spaces. The complexity for such an algorithm might be very high when the number of variables or samples is huge. We introduce a gradient descent algorithm for gradient learning in classification. The implementation of this algorithm is simple and its convergence is elegantly studied. Explicit learning rates are presented in terms of the regularization parameter and the step size. Deep analysis for approximation by reproducing kernel Hilbert spaces under some mild conditions on the probability measure for sampling allows us to deal with a general class of convex loss functions.     

一种新的非单调谱共轭梯度算法

提出了一类新的非单调谱共轭梯度方法.该方法通过引入混合因子,将HS方法和PRP方法结合得到共轭系数的新的选取方式.以此为基础,通过合适地选取谱系数保证了所有搜索方向不依赖于线搜索条件,恒为充分下降方向.其次,该方法还修正了Zhang和Hager提出的非单调线搜索规则,在更弱的假设条件下证明了全局收敛性.数值试验说明了该方法的计算性能优良.     

模糊自组织特征映射模型

本文提出了一种模糊自组织特征映射模型算法，它将模糊ｃ－均值模型结合到Ｋｏｈｏｎｅｎ自组织算法的学习和更新策略中，从而将神经元的侧抑制作用与模糊控制策略有机地结合起来；不仅实现了关于模糊ｃ－均值的优化问题，而且还通过隶属函数的重新构造最终构成了自组织有序拓扑图。仿真结果表明收敛性得到了很大提高。     

求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法

增广拉格朗日方法是求解带线性约束的凸优化问题的有效算法.线性化增广拉格朗日方法通过线性化增广拉格朗日函数的二次罚项并加上一个临近正则项,使得子问题容易求解,其中正则项系数的恰当选取对算法的收敛性和收敛速度至关重要.较大的系数可保证算法收敛性,但容易导致小步长.较小的系数允许迭代步长增大,但容易导致算法不收敛.本文考虑求解带线性等式或不等式约束的凸优化问题.我们利用自适应技术设计了一类不定线性化增广拉格朗日方法,即利用当前迭代点的信息自适应选取合适的正则项系数,在保证收敛性的前提下尽量使得子问题步长选择范围更大,从而提高算法收敛速度.我们从理论上证明了算法的全局收敛性,并利用数值实验说明了算法的有效性.     

Convergence presque sûre de l'algorithme de Kohonen unidimensionnel

We prove the a.s. convergence of the one dimensional Kohonen algorithm after selforganization and with decreasing step. Under some mild asumption of log-concavity on the input probability distribution, we first show the uniqueness of the limit and then the a.s. convergence. The proof relies on the index formula for a vector field on a manifold and a result by M. Hirsh about the convergence of cooperative dynamical systems applied to the ODE.     

Backfitting neural networks

Summary  Regression and classification problems can be viewed as special cases of the problem of function estimation. It is rather well known that a two-layer perceptron with sigmoidal transformation functions can approximate any continuous function on the compact subsets ofRP if there are sufficient number of hidden nodes. In this paper, we present an algorithm for fitting perceptron models, which is quite different from the usual backpropagation or Levenberg-Marquardt algorithm. This new algorithm based on backfitting ensures a better convergence than backpropagation. We have also used resampling techniques to select an ideal number of hidden nodes automatically using the training data itself. This resampling technique helps to avoid the problem of overfitting that one faces for the usual perceptron learning algorithms without any model selection scheme. Case studies and simulation results are presented to illustrate the performance of this proposed algorithm.     

Linear dynamic approximation theory

We study in detail the behavior of some known learning algorithms. We estimate the sum of the squares of the absolute relative errors of some general linear learning algorithms and the sum of the squares of the coefficients obtained by the perceptron algorithm. We prove the convergence of a statistical learning algorithm. The possibility of applications of this theory to biology is discussed.     

Strong convergence of the forward–backward splitting method with multiple parameters in Hilbert spaces

Many problems arising from machine learning, signal & image recovery, and compressed sensing can be casted into a monotone inclusion problem for finding a zero of the sum of two monotone operators. The forward–backward splitting algorithm is one of the most powerful and successful methods for solving such a problem. However, this algorithm has only weak convergence in the infinite dimensional settings. In this paper, we propose a new modification of the FBA so that it possesses a norm convergent property. Moreover, we establish two strong convergence theorems of the proposed algorithms under more general conditions.