Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-27T23:59:47.883Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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