We are interested in synthesizing and analyzing stochastic approximation algorithms for distributed optimization. How quickly can a constant step size stochastic approximation track a time varying parameter or more generally, the equilibria of a time varying game? Stochastic averaging theory is the main tool that we use to analyze such algorithms. One of our major results is that if the parameter jumps according to a Markov chain with slow transition matrix, then the asymptotic behavior of the stochastic approximation converges to a switched-Markovian ordinary differential equation or differential inclusion. Our work is in collaboration with George Yin of Wayne State University, who is the expert in weak convergence analysis.
Related Papers
-
O. Namvar, V.Krishnamurthy, G, Yin, Adaptive Search Algorithms for Discrete Stochastic Optimization: A Smooth Best-Response Approach, IEEE Trans Automatic Control, 2016.
-
M. Hamdi, V. Krishnamurthy, G. Yin, Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph, IEEE Transactions Information Theory, 2014.
-
O. Namvar, V. Krishnamurthy and G. Yin, Distributed Tracking of Correlated – Equilibria in Regime Switching Noncooperative Games, IEEE Transactions Automatic Control, pp.2435–2450, 2013.
-
O. Namvar. V. Krishnamurthy and G. Yin, Distributed Energy-Aware Diffusion Least Mean Squares: Game-Theoretic Learning, IEEE Journal Selected Topics in Signal Processing, Vol.7, No.5, pp.821–836, 2013.
-
V. Krishnamurthy, F. Vazquez-Abad, Gradient Based Policy Optimization of Constrained Unichain Markov Decision Processes, Festschrift for Robert Elliott’s 70th Birthday, World Scientific, 2012.
-
V. Krishnamurthy, K. Topley and G. Yin, Consensus Formation in a two-time-scale Markovian System, SIAM Journal Multiscale Modeling and Simulation, Vol.7, No.4, pp.1898–1927, 2009.
-
G. Yin, C. Ion and V. Krishnamurthy, How does a Stochastic Approximation Algorithm Adapt to a Randomly Evolving Optimum with Jump Markov Sample Paths, Mathematical Programming B., (Special Issue dedicated to B.T. Polyak’s 70th Birthday), Vol.120, No.1, pp.67–99, 2009.
-
G. Yin and V. Krishnamurthy, Analysis of LMS Algorithm for Slowly Varying Markovian Parameters – Tracking Slow Hidden Markov Models and Adaptive Multiuser Detection in DS/CDMA, IEEE Transactions Information Theory, Vol.51, No.7, pp.2475– 2490, July 2005
-
G. Yin and V. Krishnamurthy, Least Mean Squares Algorithms with Markov Regime Switching Limit, IEEE Transactions Automatic Control, Vol.50, No.5, pp.577–593, May 2005.
-
V. Krishnamurthy, X. Wang and G.Yin, Spreading Code Optimization and Adaptation in CDMA via Discrete Stochastic Approximation, IEEE Transactions on Information Theory, Vol.50, No.9, pp.1927–1949, Sept.2004.
-
G. Yin, V. Krishnamurthy and C. Ion, Regime Switching Stochastic Approximation Algorithms with Application to Adaptive Discrete Stochastic Optimization, SIAM Journal on Optimization, Vol.14, No.4, pp.1187–1215, 2004.
-
V. Krishnamurthy and G. Yin, Recursive Algorithms for Estimation of Hidden Markov Models and Autoregressive Models with Markov Regime, IEEE Transactions on Information Theory, Vol.48, No.2, pp.458-476, Feb 2002.