Project B5: Probabilistic analysis and algorithms in stochastic fixed point theory

This project seeks to apply tools from probability theory to the analysis of fixed point algorithms. Fixed point algorithms are at the foundation of numerical methods for solving partial differential equations, problems in optimization, and computing probability distributions. This research consists of two complementary threads. One thread concerns generalizations of deterministic fixed point algorithms where stochastic parameters enter into the iterations. The second thread seeks to apply probabilistic techniques to the analysis of the convergence of random selections of (possibly infinite) collections of operators, with applications to algorithms for large-scale optimization problems.

In this project one main focus so far has been on random function iterations for solving stochastic fixed point problems involving operators with specific properties such as nonexpansivity and averagedness that had previously been studied in a deterministic setting. We have analyzed convergence properties of these stochastic algorithms, which in this setting are Markov chains, in the case of consistent and inconsistent feasibility problems. We will in the future apply this analysis to general recursive distributional equations and corresponding recursive tree processes. Another goal will be to provide a more quantitative analysis of random function iterations.

Methods: variational analysis, probabilistic techniques and convergence, optimization under uncertainty, recursive distributional equations
Applications: (stochastic) fixed point problems, image deconvolution/denoising with probabilistic constraints, distributed computation, optimal mass transport