AF: Small: A New Approach to Analysis and Design of Algorithms for Stochastic Control and Optimization

University Of Southern California, Los Angeles CA

Investigators

Abstract

Randomized algorithms for stochastic optimization and control underpin many developing technologies such as Artificial Intelligence (AI), Autonomous Robotics, and Big Data Analytics. Their development is hampered by a lack of suitable mathematical tools. In many cases, current mathematical techniques such as those based on Stochastic Lyapunov theory are rather difficult to use, thus necessitating invention of customized techniques for algorithm design for each problem and its analysis. This project will develop a new class of mathematical techniques, called probabilistic contraction analysis, that are easier to use, and more broadly applicable. The project's aim is not just analysis of existing algorithms, but development of analysis tools with an eye on design. The project outcomes can accelerate development of new algorithms for stochastic control and optimization problems that arise in many important application fields such as AI, Autonomy, Big Data Analytics, etc. The project will train under-represented and/or female PhD students and postdocs, as well as high school students and teachers. Given a randomized algorithm for stochastic optimization and control, this project views each iteration as applying a random operator, and develops new "probabilistic contraction" analysis techniques, created by the investigator, that use stochastic dominance arguments to show convergence to probabilistic fixed points. Specifically, the investigator will develop empirically-inspired algorithms for optimal control of continuous state and action space Markov decision processes, and unconstrained and constrained stochastic optimization problems. The techniques to be developed may be useful for a broader class of stochastic iterative algorithms, and lead to development of a probabilistic fixed point theory of random operators on Banach spaces. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.