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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A generalized Polya's urn with graph based interactions

引用

RANDOM STRUCTURES & algorithms 2015年第4期46卷 614-634页

作者： Benaim, Michel Benjamini, Itai Chen, Jun Lima, Yuri Univ Neuchatel Inst Math CH-2000 Neuchatel Switzerland Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel Univ Maryland Dept Math College Pk MD 20742 USA

Given a finite connected graph G, place a bin at each vertex. Two bins are called a pair if they share an edge of G. At discrete times, a ball is added to each pair of bins. In a pair of bins, one of the bins gets the ball with probability proportional to its current number of balls raised by some fixed power >0. We characterize the limiting behavior of the proportion of balls in the bins. The proof uses a dynamical approach to relate the proportion of balls to a vector field. Our main result is that the limit set of the proportion of balls is contained in the equilibria set of the vector field. We also prove that if <1 then there is a single point v=v(G,) with non-zero entries such that the proportion converges to v almost surely. A special case is when G is regular and 1. We show e.g. that if G is non-bipartite then the proportion of balls in the bins converges to the uniform measure almost *** (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,614-634, 2015

关键词： gradient-like system Polya's urn reinforcement stochastic approximation algorithms unstable equilibria

来源：评论

学校读者我要写书评

暂无评论

Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第10期60卷 6609-6625页

作者： Hamdi, Maziyar Krishnamurthy, Vikram Yin, George Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Wayne State Univ Dept Math Detroit MI 48202 USA

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network;the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. Two results are presented. First, motivated by social network applications, the asymptotic behavior of the degree distribution is analyzed. Second, a stochastic approximation algorithm is presented to track empirical degree distribution as it evolves over time. The tracking performance of the algorithm is analyzed in terms of mean square error and a functional central limit theorem is presented for the asymptotic tracking error. Also, a Hilbert-space-valued stochastic approximation algorithm that tracks a Markov-modulated probability mass function with support on the set of nonnegative integers is analyzed.

关键词： Adaptive algorithms complex networks degree distribution Markov-modulated random graphs power law social networks stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Two particles' repelling random walks on the complete graph

引用

ELECTRONIC JOURNAL OF PROBABILITY 2014年第none期19卷 1-17页

作者： Chen, Jun CALTECH Div Humanities & Social Sci Pasadena CA 91125 USA

We consider two particles' repelling random walks on complete graphs. In this model, each particle has higher probability to visit the vertices which have been seldom visited by the other one. By a dynamical approach we prove that the two particles' occupation measure asymptotically has small joint support almost surely if the repulsion is strong enough.

关键词： Repelling random walks Reinforced random walk multi-particle complete graph stochastic approximation algorithms dynamical approach chain recurrent set Lyapunov function

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimal multi-layered congestion based pricing schemes for enhanced QoS

引用

COMPUTER NETWORKS 2012年第4期56卷 1249-1262页

作者： Vemu, Koteswara Rao Bhatnagar, Shalabh Hemachandra, N. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Indian Inst Technol Dept Ind Engn & Operat Res Bombay 400076 Maharashtra India

Pricing is an effective tool to control congestion and achieve quality of service (QoS) provisioning for multiple differentiated levels of service. In this paper, we consider the problem of pricing for congestion control in the case of a network of nodes with multiple queues and multiple grades of service. We present a closed-loop multi-layered pricing scheme and propose an algorithm for finding the optimal state dependent price levels for individual queues, at each node. This is different from most adaptive pricing schemes in the literature that do not obtain a closed-loop state dependent pricing policy. The method that we propose finds optimal price levels that are functions of the queue lengths at individual queues. Further, we also propose a variant of the above scheme that assigns prices to incoming packets at each node according to a weighted average queue length at that node. This is done to reduce frequent price variations and is in the spirit of the random early detection (RED) mechanism used in TCP/IP networks. We observe in our numerical results a considerable improvement in performance using both of our schemes over that of a recently proposed related scheme in terms of both throughput and delay performance. In particular, our first scheme exhibits a throughput improvement in the range of 67-82% among all routes over the above scheme. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Optimal multi-layered pricing Closed loop feedback policies SPSA stochastic approximation algorithms Disutility

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Erratum: Concentration bounds for stochastic approximation

引用

Electronic Communications in Probability 2012年第NONE期17卷 1-2页

作者： Noufel Frikha Stéphane Menozzi

This is an erratum for paper "Concentration bounds for stochastic approximation" appeared in ECP volume 17 paper number 47

关键词： 60H35 65C05 65C30 Euler scheme Gaussian concentration Non asymptotic bounds stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：