检索结果-内蒙古大学图书馆

Monte-Carlo estimation of time-dependent statistical characteristics of random dynamical systems

APPLIED MATHEMATICAL MODELLING 2011年第6期35卷 3063-3079页

作者： Bhatnagar, Shalabh Karmeshu Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Jawaharlal Nehru Univ Sch Comp & Syst Sci New Delhi 110067 India

The problem of estimating the time-dependent statistical characteristics of a random dynamical system is studied under two different settings. In the first, the system dynamics is governed by a differential equation parameterized by a random parameter, while in the second, this is governed by a differential equation with an underlying parameter sequence characterized by a continuous time Markov chain. We propose, for the first time in the literature, stochastic approximation algorithms for estimating various time-dependent process characteristics of the system. In particular, we provide efficient estimators for quantities such as the mean, variance and distribution of the process at any given time as well as the joint distribution and the autocorrelation coefficient at different times. A novel aspect of our approach is that we assume that information on the parameter model (i.e., its distribution in the first case and transition probabilities of the Markov chain in the second) is not available in either case. This is unlike most other work in the literature that assumes availability of such information. Also, most of the prior work in the literature is geared towards analyzing the steady-state system behavior of the random dynamical system while our focus is on analyzing the time-dependent statistical characteristics which are in general difficult to obtain. We prove the almost sure convergence of our stochastic approximation scheme in each case to the true value of the quantity being estimated. We provide a general class of strongly consistent estimators for the aforementioned statistical quantities with regular sample average estimators being a specific instance of these. We also present an application of the proposed scheme on a widely used model in population biology. Numerical experiments in this framework show that the time-dependent process characteristics as obtained using our algorithm in each case exhibit excellent agreement with exact results. (C) 2010 El

关键词： Random dynamical systems Random differential equations stochastic differential equations Continuous time Markov chains Monte-Carlo estimates stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

THE stochastic AUXILIARY PROBLEM PRINCIPLE IN BANACH SPACES: MEASURABILITY AND CONVERGENCE

引用

SIAM JOURNAL ON OPTIMIZATION 2022年第3期32卷 1871-1900页

作者： Bittar, Thomas Carpentier, Pierre Chancelier, Jean-Philippe Lonchampt, Jerome EDF R&D Chatou France ENSTA Paris Inst Polytech Paris UMA Paris France Ecole Ponts ParisTech CERMICS Paris France

The stochastic auxiliary problem principle (APP) algorithm is a general stochastic approximation (SA) scheme that turns the resolution of an original convex optimization problem into the iterative resolution of a sequence of auxiliary problems. This framework has been introduced to design decomposition-coordination schemes but also encompasses many well-known SA algorithms such as stochastic gradient descent or stochastic mirror descent. We study the stochastic APP in the case where the iterates lie in a Banach space and we consider an additive error on the computation of the subgradient of the objective. In order to derive convergence results or efficiency estimates for an SA scheme, the iterates must be random variables. This is why we prove the measurability of the iterates of the stochastic APP algorithm. Then, we extend convergence results from the Hilbert space case to the reflexive separable Banach space case. Finally, we derive efficiency estimates for the function values taken at the averaged sequence of iterates or at the last iterate, the latter being obtained by adapting the concept of modified Fej\'er monotonicity to our framework.

关键词： stochastic auxiliary problem principle APP stochastic approximation algorithms SA algorithms stochastic gradient descent stochastic mirror descent

来源：评论

学校读者我要写书评

暂无评论

Multi-Time Scale Smoothed Functional With Nesterov's Acceleration

引用

IEEE ACCESS 2021年 9卷 113489-113499页

作者： Sharma, Abhinav Lakshmanan, K. Gupta, Ruchir Gupta, Atul PDPM Indian Inst Informat Technol Jabalpur Dept Comp Sci Jabalpur 482005 Madhya Pradesh India IIT Banaras Hindu Univ BHU Varanasi Dept Comp Sci Varanasi 221005 Uttar Pradesh India Jawaharlal Nehru Univ JNU Dept Comp Sci Delhi 110067 India

Smoothed functional (SF) algorithm estimates the gradient of the stochastic optimization problem by convolution with a smoothening kernel. This process helps the algorithm to converge to a global minimum or a point close to it. We study a two-time scale SF based gradient search algorithm with Nesterov's acceleration for stochastic optimization problems. The main contribution of our work is to prove the convergence of this algorithm using the stochastic approximation theory. We propose a novel Lyapunov function to show the associated second-order ordinary differential equations' (o.d.e.) stability for a non-autonomous system. We compare our algorithm with other smoothed functional algorithms such as Quasi-Newton SF, Gradient SF and Jacobi Variant of Newton SF on two different optimization problems: first, on a simple stochastic function minimization problem, and second, on the problem of optimal routing in a queueing network. Additionally, we compared the algorithms on real weather data in a weather prediction task. Experimental results show that our algorithm performs significantly better than these baseline algorithms.

关键词： approximation algorithms Linear programming Convergence Prediction algorithms Markov processes Cost function Trajectory Multi-Stage queueing networks Nesterov's acceleration simulation smoothed functional algorithm stochastic approximation algorithms stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

Strong error analysis for stochastic gradient descent optimization algorithms

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2021年第1期41卷 455-492页

作者： Jentzen, Arnulf Kuckuck, Benno Neufeld, Ariel von Wurstemberger, Philippe Univ Munster Fac Math & Comp Sci D-48149 Munster Germany NTU Singapore Div Math Sci Singapore 637371 Singapore Swiss Fed Inst Technol Dept Math CH-8092 Zurich Switzerland

stochastic gradient descent (SGD) optimization algorithms are key ingredients in a series of machine learning applications. In this article we perform a rigorous strong error analysis for SGD optimization algorithms. In particular, we prove for every arbitrarily small epsilon is an element of (0,infinity) and every arbitrarily large p epsilon (0,infinity) that the considered SGD optimization algorithm converges in the strong L-p-sense with order 1/2-epsilon to the global minimum of the objective function of the considered stochastic optimization problem under standard convexity-type assumptions on the objective function and relaxed assumptions on the moments of the stochastic errors appearing in the employed SGD optimization algorithm. The key ideas in our convergence proof are, first, to employ techniques from the theory of Lyapunov-type functions for dynamical systems to develop a general convergence machinery for SGD optimization algorithms based on such functions, then, to apply this general machinery to concrete Lyapunov-type functions with polynomial structures and, thereafter, to perform an induction argument along the powers appearing in the Lyapunov-type functions in order to achieve for every arbitrarily large p epsilon (0,infinity) strong L-p-convergence rates.

关键词： stochastic gradient descent stochastic approximation algorithms Strong error analysis

来源：评论

学校读者我要写书评

暂无评论

stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

引用

stochasticS-AN INTERNATIONAL JOURNAL OF PROBABILITY AND stochastic REPORTS 2016年第8期88卷 1173-1187页

作者： Ramaswamy, Arunselvan Bhatnagar, Shalabh Indian Inst Sci Dept Comp Sci & Automat Bangalore Karnataka India

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.

关键词： Set-valued dynamical systems Lagrangian dual optimization and control stochastic approximation algorithms differential inclusions two timescales constrained optimization 62L20 93E03 93E35 34A60 90C31

来源：评论

学校读者我要写书评

暂无评论

Concentration bounds for stochastic approximations (vol 17, pg 1, 2012)

引用

ELECTRONIC COMMUNICATIONS IN PROBABILITY 2012年第none期17卷 1-2页

作者： Frikha, Noufel Menozzi, Stephane Univ Paris 07 Paris France Univ Evry Val dEssonne Evry France

We correct an error in [2] pointed out to us by Bernard Bercu.

关键词： Non asymptotic bounds Euler scheme stochastic approximation algorithms Gaussian concentration

来源：评论

学校读者我要写书评

暂无评论

An adaptive version for the Metropolis Adjusted Langevin algorithm with a truncated drift

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2006年第2期8卷 235-254页

作者： Atchade, Yves F. Univ Ottawa Dept Math & Stat Ottawa ON K1N 6N5 Canada

This paper extends some adaptive schemes that have been developed for the Random Walk Metropolis algorithm to more general versions of the Metropolis-Hastings (MH) algorithm, particularly to the Metropolis Adjusted Langevin algorithm of Roberts and Tweedie (1996). Our simulations show that the adaptation drastically improves the performance of such MH algorithms. We study the convergence of the algorithm. Our proves are based on a new approach to the analysis of stochastic approximation algorithms based on mixingales theory.

关键词： adaptive Markov Chain Monte Carlo Langevin algorithms Metropolis-Hastings algorithms stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

CENTRAL LIMIT THEOREMS OF A RECURSIVE stochastic ALGORITHM WITH APPLICATIONS TO ADAPTIVE DESIGNS

引用

ANNALS OF APPLIED PROBABILITY 2016年第6期26卷 3630-3658页

作者： Zhang, Li-Xin Zhejiang Univ Sch Math Sci Zheda Rd 38 Hangzhou 310027 Zhejiang Peoples R China

stochastic approximation algorithms have been the subject of an enormous body of literature, both theoretical and applied. Recently, Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409-1436] presented a link between the stochastic approximation and response-adaptive designs in clinical trials based on randomized urn models investigated in Bai and Hu [stochastic Process. Appl. 80 (1999) 87-101;Ann. Appl. Probab. 15 (2005) 914-940], and derived the asymptotic normality or central limit theorem for the normalized procedure using a central limit theorem for the stochastic approximation algorithm. However, the classical central limit theorem for the stochastic approximation algorithm does not include all cases of its regression function, creating a gap between the results of Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409-1436] and those of Bai and Hu [Ann. Appl. Probab. 15 (2005) 914-940] for randomized urn models. In this paper, we establish new central limit theorems of the stochastic approximation algorithm under the popular Lindeberg condition to fill this gap. Moreover, we prove that the process of the algorithms can be approximated by a Gaussian process that is a solution of a stochastic differential equation. In our application, we investigate a more involved family of urn models and related adaptive designs in which it is possible to remove the balls from the urn, and the expectation of the total number of balls updated at each stage is not necessary a constant. The asymptotic properties are derived under much less stringent assumptions than those in Bai and Hu [stochastic Process. Appl. 80 (1999) 87-101;Ann. Appl. Probab. 15 (2005) 914-940] and Laruelle and Pages [Ann. Appl. Probab. 23 (2013) 1409-1436].

关键词： stochastic approximation algorithms central limit theorem urn model adaptive design Gaussian approximation the ODE method

来源：评论

学校读者我要写书评

暂无评论

Transport-Entropy inequalities and deviation estimates for stochastic approximations schemes

引用

ELECTRONIC JOURNAL OF PROBABILITY 2013年第none期18卷 1-36页

作者： Fathi, Max Frikha, Noufel Univ Paris 06 LPMA Paris France Univ Paris Diderot LPMA Paris France

We obtain new transport-entropy inequalities and, as a by-product, new deviation estimates for the laws of two kinds of discrete stochastic approximation schemes. The first one refers to the law of an Euler like discretization scheme of a diffusion process at a fixed deterministic date and the second one concerns the law of a stochastic approximation algorithm at a given time-step. Our results notably improve and complete those obtained in [10]. The key point is to properly quantify the contribution of the diffusion term to the concentration regime. We also derive a general non-asymptotic deviation bound for the difference between a function of the trajectory of a continuous Euler scheme associated to a diffusion process and its mean. Finally, we obtain non-asymptotic bound for stochastic approximation with averaging of trajectories, in particular we prove that averaging a stochastic approximation algorithm with a slow decreasing step sequence gives rise to optimal concentration rate.

关键词： deviation bounds transportation-entropy inequalities Euler scheme stochastic approximation algorithms stochastic approximation with averaging

来源：评论

学校读者我要写书评

暂无评论

On the Convergence of Smoothed Functional stochastic Optimization algorithms

引用

IFAC-PapersOnLine 2015年第28期48卷 229-233页

作者： Chen, Xing-Min Gao, Chao School of Mathematical Sciences Dalian University of Technology Dalian116024 China School of Information Science and Engineering Dalian Polytechnic University Dalian116034 China

Smoothed functional gradient algorithm with perturbations distributed according to the Gaussian distribution is considered for stochastic optimization problem with additive noise. A stochastic approximation algorithm with expanding truncations that uses either one-sided or two-sided gradient estimate is given. At each iteration of the algorithm only two observations are required. The algorithm is shown to be convergent under only some mild conditions © 2015

关键词： approximation algorithms Additive noise approximation theory Iterative methods Optimization stochastic systems Functional estimate Functional gradient Simultaneous perturbation stochastic approximation stochastic approximation algorithms stochastic optimization algorithm stochastic optimization problems stochastic optimizations Strong consistency

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：