A Geometric Framework for Stochastic Algorithms in Feasibility and Inclusion Problems

North Carolina State University, Raleigh NC

Investigators

Abstract

Mathematical models arising in areas such as data analysis, artificial intelligence, geophysics, signal processing, and medical imaging are increasingly complex due to their large size and the presence of random perturbations. This project will investigate foundational principles governing the mathematical representation and the numerical solution of such large-scale random models. New strategies and methodologies based on geometric principles to effectively incorporate randomness in the underlying mathematical representations and in the design of efficient randomized solution algorithms will be developed. Graduate students will be trained as part of the research plan. This project focuses on models and convergence principles for dealing with stochasticity in a wide range of algorithms for solving various types of equilibrium problems arising in convex feasibility, best approximation, convex optimization, fixed point, variational inequality, and monotone inclusion problems. A flexible geometric framework will be developed that captures a broad array of existing algorithms while furnishing an effective pattern for designing new ones. The tools to be developed in the project aim at providing common principles to analyze the asymptotic behavior of stochastic algorithms at several levels: stochastic operator approximations, random coordinate updates, and random operator activations. The two generic classes of problems considered are convex feasibility problems and multivariate systems of structured monotone inclusions. Extensions beyond the monotone/convex setting are also planned. The theoretical and algorithmic findings will be applied to problems in the areas of signal processing, artificial intelligence, machine learning, inverse problems, statistical biology, and medical imaging. 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.