Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T02:36:08.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Forward sensitivity analysis for contracting stochastic systems

Part of: Markov processes Numerical problems in dynamical systems

Published online by Cambridge University Press:  20 March 2018

Thomas Flynn
Thomas Flynn*
Affiliation:
City University of New York
*
* Current address: Computational Science Initiative, Brookhaven National Laboratory, P.O. Box 5000, Upton, NY 11973, USA. Email address: tflynn@bnl.gov
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we investigate gradient estimation for a class of contracting stochastic systems on a continuous state space. We find conditions on the one-step transitions, namely differentiability and contraction in a Wasserstein distance, that guarantee differentiability of stationary costs. Then we show how to estimate the derivatives, deriving an estimator that can be seen as a generalization of the forward sensitivity analysis method used in deterministic systems. We apply the results to examples, including a neural network model.

Keywords

Markov chainderivative estimationcontractioniterated function system

MSC classification

Primary: 60J05: Discrete-time Markov processes on general state spaces
Secondary: 90C31: Sensitivity, stability, parametric optimization 65P99: None of the above, but in this section
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 1 , March 2018 , pp. 102 - 130
Copyright
Copyright © Applied Probability Trust 2018 

References

[1] Borovkov, A. A. and Hordijk, A. (2004). Characterization and sufficient conditions for normed ergodicity of Markov chains. Adv. Appl. Prob. 36, 227–242. CrossRefGoogle Scholar
[2] Burago, D., Burago, Y. and Ivanov, S. (2001). A Course in Metric Geometry (Graduate Stud. Math. 33). American Mathematical Society, Providence, RI. CrossRefGoogle Scholar
[3] Flynn, T. (2015). Timescale separation in recurrent neural networks. Neural Comput. 27, 1321–1344. CrossRefGoogle ScholarPubMed
[4] Flynn, T. (2016). Convergence of one-step adjoint methods. In Proceedings of the 22nd International Symposium on Mathematical Theory of Networks and Systems. Google Scholar
[5] Forni, F. and Sepulchre, R. (2014). A differential Lyapunov framework for contraction analysis. IEEE Trans. Automatic Control 59, 614–628. CrossRefGoogle Scholar
[6] Griewank, A. and Walther, A. (2008). Evaluating Derivatives, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA. CrossRefGoogle Scholar
[7] Hairer, M. (2006). Ergodic properties of Markov processes. Lecture given at the University of Warwick. Available at http://www.hairer.org/notes/Markov.pdf. Google Scholar
[8] Hairer, M. and Mattingly, J. C. (2008). Spectral gaps in Wasserstein distances and the 2D stochastic Navier–Stokes equations. Ann. Prob. 36, 2050–2091. CrossRefGoogle Scholar
[9] Heidergott, B. and Hordijk, A. (2003). Taylor series expansions for stationary Markov chains. Adv. Appl. Prob. 35, 1046–1070. (Correction: 36 (2004), 1300.) CrossRefGoogle Scholar
[10] Heidergott, B., Hordijk, A. and Weisshaupt, H. (2006). Measure-valued differentiation for stationary Markov chains. Math. Operat. Res. 31, 154–172. CrossRefGoogle Scholar
[11] Joulin, A. and Ollivier, Y. (2010). Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann. Prob. 38, 2418–2442. CrossRefGoogle Scholar
[12] Lohmiller, W. and Slotine, J.-J. E. (1998). On contraction analysis for non-linear systems. Automatica J. 34, 683–696. CrossRefGoogle Scholar
[13] Pflug, G. C. (1992). Gradient estimates for the performance of Markov chains and discrete event processes. Ann. Operat. Res. 39, 173–194. CrossRefGoogle Scholar
[14] Pflug, G. C. (1996). Optimization of Stochastic Models: The Interface Between Simulation and Optimization. Kluwer, Boston, MA. CrossRefGoogle Scholar
[15] Pineda, F. J. (1988). Dynamics and architecture for neural computation. J. Complexity 4, 216–245. CrossRefGoogle Scholar
[16] Rumelhart, D. E., Hinton, G. E. and Williams, R. J. (1986). Learning representations by back-propagating errors. Nature 323, 533–536. CrossRefGoogle Scholar
[17] Russo, G., di Bernardo, M. and Sontag, E. D. (2010). Global entrainment of transcriptional systems to periodic inputs. PLoS Comput. Biol. 6, e1000739. CrossRefGoogle ScholarPubMed
[18] Simpson-Porco, J. W. and Bullo, F. (2014). Contraction theory on Riemannian manifolds. Systems Control Lett. 65, 74–80. CrossRefGoogle Scholar
[19] Steinsaltz, D. (1999). Locally contractive iterated function systems. Ann. Prob. 27, 1952–1979. CrossRefGoogle Scholar
[20] Stenflo, Ö. (2012). A survey of average contractive iterated function systems. J. Difference Equat. Appl. 18, 1355–1380. CrossRefGoogle Scholar
[21] Vázquez-Abad, F. J. and Kushner, H. J. (1992). Estimation of the derivative of a stationary measure with respect to a control parameter. J. Appl. Prob. 29, 343–352. CrossRefGoogle Scholar
[22] Villani, C. (2009). Optimal Transport: Old and New. Springer, Berlin. CrossRefGoogle Scholar